基于快排的疾速抉择算法
-
问题
最近做到一个经典的 leetcode 题目,因为分类在“分治算法”标签中,故思考用分治的思维解决,题目如下,
剑指 offer40. 最小的 k 个数
输出整数数组 arr,找出其中最小的 k 个数。例如,输出 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4。
示例 1:
输出:arr = [3,2,1], k = 2 输入:[1,2] 或者 [2,1]
示例 2:
输出:arr = [0,1,2,1], k = 1 输入:[0]
本题有三种解法,别离是简略粗犷的 排序 而后取前 k 个数,基于 堆排序 的一种改良算法,以及本文所讲的 疾速抉择算法。第一种办法实际上是将数组中的所有元素先排序,而后取前 k 个,然而咱们想真的有必要将所有元素一次性的进行排序吗?咱们只须要晓得最小的 k 个元素即可,所以咱们是否能够对局部元素进行排序,而后判断再对局部元素进行排序,一旦达到咱们的指标(曾经筛选出 k 个元素了),全身而退。实践上这是要比一次性排序所需的工夫少得多的。第二种和第三种办法都带有这类思维。
- 回顾疾速排序
在快排中也是使用了分治的思维,每一次排序中,咱们会在数组中抉择一个元素作为枢轴(能够了解为杠杆点,个别抉择数组第一个点,当然也能够随机抉择),通过双指针 low,high 将比这个枢轴元素小的元素放在它的左侧,比它大的元素放在它的右侧。这样就实现了一次初步的排序,以这个枢轴为中心点能够划分成左右两块,右边的元素都比枢轴小,左边的元素都比枢轴大。进而对左右两个子数组再次进行以上的步骤,这也体现了分而治之的思维。具体过程看下图,
疾速排序外围代码如下,
while(lo < hi){while(lo<hi && arr[hi] >= pivotkey)hi--;
arr[lo] = arr[hi];
while(lo<hi && arr[lo] <= pivotkey)lo++;
arr[hi]=arr[lo];
}
arr[lo]=pivotkey;
- 疾速抉择的原理
疾速抉择就是在上述根底上进行革新的,咱们能够看到,上图中曾经通过一个杠杆点将数组分成了左右两块,称为左块和右块,左块的元素必定比杠杆点小或等于,那么因为题目中是要求咱们选取最小的 k 个点,咱们假如 k 等于 4,那么上图中曾经达到了咱们的指标,间接返回杠杆点的下标即可。也就是 low+1-start == k 即返回 low,其中 start 为 low 刚进来的值,因为 low 的初值不肯定都是 0,用 lo+1-start 示意左块的元素个数。
上面思考若 low-start+1 < k,这阐明左块的元素数量还不够,然而左块中的元素和杠杆点必定曾经是最小 k 个元素中的了,所以咱们只须要递归一次,对lo+1,nums.size()-1 区间上的元素再找出 k-(low+1-start), 就能够返回这个区间上的杠杆点的坐标即为最终的后果。
若 low-start+1 > k, 这阐明左块的元素太多了,那么咱们就能够齐全舍弃右块,在区间start,lo-1 上找到 k 个最小元素即可。
这有点像一种变相的分治,即分完之后并不对每一个块进行治理,而是有抉择的进行治理。
- 疾速抉择的代码实现
int Partition(vector<int>& arr,int lo,int hi,int k){if(hi - lo + 1 == k)return hi; // 留神:若传进来区间的长度曾经等于 k 了,那么没必要快排了,间接返回即可。int start = lo; // 不然很难选中一个刚刚好的杠杆点,从而会造成重复横跳的状况。int pivotkey = arr[lo];
while(lo < hi){ // 快排外围代码
while(lo<hi && arr[hi] >= pivotkey)hi--;
arr[lo] = arr[hi];
while(lo<hi && arr[lo] <= pivotkey)lo++;
arr[hi]=arr[lo];
}
arr[lo]=pivotkey;
if(lo-start+1 == k)return lo; // 返回杠杆点的下标
else if(lo-start+1 < k){return Partition(arr,lo+1,arr.size()-1,k-(lo-start+1));
}
else{return Partition(arr,start,lo-1,k);
}
}