给定一个既包含负值又包含正值的数组,我如何找到最接近中位数的第k个元素?我有一个快速选择方法,可以找到数组的中位数。然后,我遍历原始数组并创建另一个数组diff
,在其中我将数组中每个元素的绝对值减去中值(abs(a[i]-median)
)。但是,我不知道如何修改我的quickselect和分区来实现此目的。这就是我目前所拥有的。
在数组a
的中间找到值:
midpoint=int(len(a)/2)
median=quickSelect(a,len(a)-1,midpoint)
quickSelect
如下所示:
def quickSelect(array,start,end,k):
if start>=end:
return array[k]
value=partition(array,end)
if value>k:
return quickSelect(array,value-1,k)
else:
return quickSelect(array,value+1,k)
和partition
方法如下:
def partition(array,end):
x=start-1
#pivot is the last element at each iteration
pivot=array[end]
for i in range(start,end):
if array[i]<=pivot:
x+=1
array[x],array[i]=array[i],array[x]
array[x+1],array[end]=array[end],array[x+1]
return x+1
然后我存储差异的绝对值:
diff=[None]*len(a)
for x in range(len(a)):
diff[x]=abs(a[x]-median)
在这一点上,我不知道要对用来查找数组中位数的新的快速选择和分区函数进行哪些修改。
具有数组[10,4,2,15,18]
和k=2
的示例输出为4,15
编辑:
我认为我已经接近解决方案,但是当数组大小较大时,我的新代码将失败。我创建了没有绝对值(diff
)的数组diff[x]=a[x]-median
然后我将值在中间的位置切换为0(diff[midpoint],diff[0]=diff[0],diff[midpoint]
),因为没有什么比中间值的绝对值减去值本身小。
然后,我创建了一个quickSelectKClosest
函数,该函数调用考虑绝对值的partitionAbsoluteValue
方法。
quickSelectKClosest
:
def quickSelectKClosest(array,k):
if start>=end:
return array[k]
value=partitionAbsoluteValue(array,end)
if value>k:
return quickSelectKClosest(array,k)
else:
return quickSelectKClosest(array,k)
partitionAbsoluteValue
:
def partitionAbsoluteValue(array,end):
x=start-1
pivot=array[end]
for i in range(start,end):
if abs(array[i])<=abs(pivot):
x+=1
array[x],array[x+1]
return x+1
然后回到main
,我这样叫quickSelectKClosest
:
val=quickSelectKClosest(diff,1,len(diff)-1,1+k)
以1作为开始,1+k
作为第k个值(因为0在diff[0]
处)
然后我发现quickSelectKClosest
返回的值的位置:
indexOfKthLargest=diff.index(val)
最后遍历diff
数组,然后将值添加到中间后面:
for x in range(1,indexOfKthLargest+1):
print(diff[x]+median)
但是如果我有一个数组:[16,-23,53,19,-39,99,84,95,7,6,64,-79,89,43,41]
和k=3
输出不完全正确:
The median was: 41
The kth closest to the median are
43
53
19
我忘了提及这一点,但是数组中的值是唯一的,因此不会重复。