LeetCode第215题目为数组中的第K个最大元素，这个题目可以用库函数sort直接排序然后完成。
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
sort函数原理是快速排序，接下来去探究一下这个算法的本质。
快速排序是由C.A.R Hoare在1960年发明的，快速排序可能是应用最广泛的排序算法了，如它名字所述，该算法的特点就是快，一般时间复杂度是O（nlgn），但是在某些特殊情况下，时间复杂度会达到（n²）。
快速排序是一种分治的排序算法。
分治就是将一个大问题，分开若干个子问题，然后求取出子问题的答案，汇总成为大问题的答案，这种特点就和递归非常贴合。
所以分治一般都是用递归去完成算法的。
所谓切分，就是选定一个元素x，然后将小于或等于x的元素都放在左边，将大于或等于x的元素都放在右边。
要完成这个实现，需要实现切分方法。
一般策略是取a[lo]作为切分元素，然后用双指针，i从左向右扫描直到找到一个大于等于x的元素，j从右往左扫描找到一个小于等于x的元素，然后交换位置。
这样是为了保证左指针i的左侧元素都 <= x， 右指针j的右侧元素都>=j。
当i 、j相遇时，我们将a[lo]和a[j]交换，然后返回j。
左指针和右指针从lo和hi + 1开始，进入循环之后先走一步然后再判断。
如果从lo + 1和hi开始，那就先判断再走。
下面代码用的是前者的情况。
int partition(vector<int> nums, int lo, int hi) {
int i = lo, j = hi + 1; //左右扫描指针
int v = nums[lo]; //切分元素
while (true) {
while (less(a[++i], v)) //先加1，再判断，直到扫描到不小于v的元素
if (i == hi) break; //如果扫描到最后，都是小于或等于v的元素，直接break
while (less(v, a[--j])) //直到扫描到不大于v的元素
if (j == lo) break;
if( i >= j) break;
swap(a[i], a[j]); //交换位置
}
swap(a[lo], a[j]); //将v放入正确的位置
return j; //返回切分位置
}
其他都好理解，就是为什么最后要和j互换有点复杂，我们举个例子运行一下算法。
第一次遍历，左指针指向了7，因为这是它遇到的第一个>=5的元素，同理右指针指向3，接下来对两个元素执行swap *** 作。
第二次遍历，左指针指向9，右指针指向2，再次进行swap *** 作。
这个时候有没有跳出扫描循环呢？并没有
第三次遍历，右指针j指向了2，左指针i指向9。
那我们知道这个时候，不能继续执行swap *** 作了，要跳出来了。
所以通过代码if( i >= j) break;跳出循环。
因为v所在的位置是左边部分，这里应该是放<=v的元素的，所以v应该和右指针j指向的元素进行交换，这样才能保证切割点左边的元素不大于v，切割点右边的元素不小于v。
最后呈现效果如上图，j是切割点，左边的子数组不大于5，但是内部暂时也是无序的，右边的子数组不小于5，内部同样无序。
通过上述切分流程，我们就成功完成了元素5的放置，在最后全部有序的队列中它的位置是不会发生改变的。
接下来就要通过递归，实现左子数组的切分和右子数组的切分，然后递归多几次，队列就完成了排序，这就是快速排序的基本流程。
库函数sort的参数是迭代器，这里用了int类型去演示，方便理解。
通过不断对左半部分排序和右半部分就可以完成最终的排序。
void sort(vector<int> &nums, int lo, int hi) {
if ( hi <= lo) return;
int j = parition(nums, lo ,hi); //切分
sort(a, lo, j - 1); //将左半部分排序
sort(a, j + 1, hi); //将右半部分排序
}
根据数学推导（具体这里就不推导），将长度为N的无重复数组排序，快速排序平均需要2NlnN次比较。
所以一般我们认为sort函数的时间复杂度和空间复杂度均为O（nlgn）。
但是快速排序最多需要约N²/2次比较，但随机打乱数组能够预防这种情况。
假设我们对已经排序的数组进行切分，而且每次只取第一个数作为切分数，就会发现左子数组永远为空，而右子数组一次减少一个，这样比较次数为N+（N-1）+ (N-2)…+ 2 + 1 = (N + 1)N/2。
这不是我们希望的情况。
有两种办法可以将此可能性降到最低，一是打乱数组，二是随机取切分数。
后面LeetCode官方题解用的就是后者。
官方题解的方法一是基于快速排序的选择方法，上文中提到的 「切分」 过程是：从子数组中选择任意一个元素 v 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， v的最终位置就是 q。
每次切分都能得到一个元素的最终位置q，只要完成n次切分，就能完成大小为n的数组排序。
但是这题仅仅需要知道倒数第k大的元素，所以只要某次切分的q位置刚好就是我们需要的倒数第k的位置，那我们就能停止算法了，至少它的左子数组和右子数组是否有序就不是我们关系的问题。
class Solution {
public:
int quickSelect(vector<int>& a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
inline int randomPartition(vector<int>& a, int l, int r) {
int i = rand() % (r - l + 1) + l; //在范围内产生随机切分数
swap(a[i], a[r]); //交换至最右边（最左边也行）
return partition(a, l, r);
}
inline int partition(vector<int>& a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a[++i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
int findKthLargest(vector<int>& nums, int k) {
//以系统时间为随机数种子
srand(time(0));
return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}
};
class Solution {
public:
int sort(vector<int>& nums, int left, int right, int index) {
int q = randomPartition(nums, left, right);
if (q == index)
return nums[q];
else
return q < index ? sort(nums, q + 1, right, index) : sort(nums, left, q - 1, index);
}
inline int randomPartition(vector<int>& nums, int left, int right) {
int k = rand() % (right - left + 1) + left; //在范围内产生随机切分数
swap(nums[k], nums[left]); //交换至最左边
int v = nums[left]; //切分数
int i = left + 1; //进一步到随机切分数的右边位置
if(i == right + 1) return left;
int j = right;
while (true) {
while (nums[i] <= v){
i++;
if(i == right + 1) break;
}
while (nums[j] >= v){
j--;
if(j == left) break;
}
//找到两个可供交换的，先判断
if (i >= j) break;
swap(nums[i], nums[j]);
}
swap(nums[left], nums[j]);
return j;
}
int findKthLargest(vector<int>& nums, int k) {
if (nums.size() == 1) return nums[0];
//以系统时间为随机数种子
srand(time(0));
return sort(nums, 0, nums.size() - 1, nums.size() - k);
}
};
修改了一下函数，方便理解。
class Solution {
public:
int sort(vector<int>& nums, int left, int right, int index) {
int q = randomPartition(nums, left, right);
if (q == index)
return nums[q];
else
return q < index ? sort(nums, q + 1, right, index) : sort(nums, left, q - 1, index);
}
inline int randomPartition(vector<int>& nums, int left, int right) {
int k = rand() % (right - left + 1) + left; //在范围内产生随机切分数
swap(nums[k], nums[left]); //交换至最左边
int v = nums[left]; //切分数
int i = left + 1; //进一步到随机切分数的右边位置
if(i == right + 1) return left;
int j = right;
while (true) {
while (nums[i] <= v){
i++;
if(i == right + 1) break;
}
while (nums[j] >= v){
j--;
if(j == left) break;
}
//找到两个可供交换的，先判断
if (i >= j) break;
swap(nums[i], nums[j]);
}
swap(nums[left], nums[j]);
return j;
}
int findKthLargest(vector<int>& nums, int k) {
if (nums.size() == 1) return nums[0];
//以系统时间为随机数种子
srand(time(0));
return sort(nums, 0, nums.size() - 1, nums.size() - k);
}
};
部分图片来自《算法 第4版》
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）