林花谢了春红
太匆匆
无奈朝来寒雨晚来风
C++，topK问题，快排的分治思想。
按照推理来说，平均复杂度应该是O(N)，最差O(N^2)。
简单来说思路就是：
- 随机在范围内指定一个元素X
- 将比元素X小的移到左边，将比元素X大的移动到右边
- 得到新的X的位置，假设为XPOS
- 然后分三种情况：
- 如果XPOS位于倒数第K位，就说明XPOS位置的这个数就是第K大了
- 如果XPOS位于倒数第K位之前，说明倒数第K大在XPOS以后，然后修改范围，重复上述1-2-3过程
- 如果XPOS位于倒数第K位以后，说明倒数第K大在XPOS之前，然后修改范围，重复上述1-2-3过程
当然对于上述第2-3步，都是“说的简单，写起来难”。。。。
这里提供一个比较好理解的实现方法，即只考虑将比X元素大的数移动到右边。
首先常规操作，将我们要定位的pivot元素找出来，并交换到序列首位，这样可以避免后续会影响该元素。
int pivot = left + rand() % (right - left + 1);
int pivot_num = nums[pivot];
swap(nums[left], nums[pivot]);
pivot = right;
然后从序列最后一个元素开始，只要大于等于pivot_num，就交换到序列尾部，同时维护一个变量pivot作为下一次交换的位置，最后所有大于等于pivot_num的元素都放到了右边，对应的pivot索引也就成了从右到左第一个小于pivot_num的元素的索引。
for (int i = right; i > left; i--) {
if (nums[i] >= pivot_num)
swap(nums[i], nums[pivot--]);
}
swap(nums[left], nums[pivot]);
当然最后别忘了将pivot交换到对应位置。
完整代码如下：
class Solution {
public:
int findKthLargest(vector<int> &nums, int k) {
srand((unsigned int) time(nullptr));
int left = 0, right = nums.size() - 1;
int pivot = -1;
while (true) {
pivot = partition(left, right, nums);
if (pivot < nums.size() - k)
left = pivot + 1;
else if (pivot > nums.size() - k)
right = pivot - 1;
else
break;
}
return nums[pivot];
}
int partition(int &left, int &right, vector<int> &nums) {
int pivot = left + rand() % (right - left + 1);
int pivot_num = nums[pivot];
swap(nums[left], nums[pivot]);
pivot = right;
for (int i = right; i > left; i--) {
if (nums[i] >= pivot_num)
swap(nums[i], nums[pivot--]);
}
swap(nums[left], nums[pivot]);
return pivot;
}
};
