这个BFPRT算法找逻辑Bug找了两天
注意点:
- 在找中位数的时候对传入的数组进行排序,这里使用直接插入排序,因为元素个数最多为5,插排常数项极低
- 注意:这里不是
而是nums[j] > nums[i]
for j = i - 1; j >= start && nums[j] > temp; j--
,因为后面会对nums[i]
造成修改
- 注意:这里不是
- 找中位数数组的中位数
medianOfMedians
返回的是最终的中位数的值,我们使用这个值进行Partition,自己这里还一直将其当做返回的索引用,导致越界 BFPRT
函数调用自己的时候,参数一定要对应,自己在写的时候直接将k传入了start