[C++知识库]高频算法面试题，TopK问题

描述：

如从海量数字中寻找最大的第 k 个数，这类问题我们称为 TOPK 问题，主要有如下解决方法：

一、基于堆来实现

• 求前 k 大，用最小堆
• 求前 k 小，用最大堆

求最大的第 K个数思路：

1、先放入元素前 k 个建立一个最小堆。

2、迭代剩余元素：
如果当前元素小于堆顶元素，跳过该元素（肯定不是前 k 大）
否则替换堆顶元素为当前元素，并重新调整堆。

3、最后获取 最小堆 中的值，即为 topk。

力扣对应的题目：LeetCode125

C++ 代码实现：

1、利用 Priority_queue实现

	1.小顶堆的实现方法
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> MinHeap;
        for(int i : nums) {
            if(MinHeap.size()<k || i>MinHeap.top())
                MinHeap.push(i);
            if(MinHeap.size() > k)
                MinHeap.pop();
        }
        return MinHeap.top();
    }

	2.大顶堆的实现方法
    int findKthLargest(vector<int>& nums, int k) {
       priority_queue<int, vector<int>, less<int>> que;
       for(int i : nums) {
           que.push(i);
       }
		
       while(--k) {		// 弹出 K-1个数，堆顶即为第K大的值
           que.pop();
       }

       return que.top();

2、手动建堆实现：

int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        buildHeap(nums, n);	// 建堆
        
        // 建堆之后进行排序，只需排好最大的 k个数即可。
        for(int i=n-1; i>n-k-1; i--) {
            swap(nums[i], nums[0]);	 // 每次的大数放最后面
            heapify(nums, i, 0);	 // 调整堆序
        }
        return nums[n-k];			 // 返回排好序的倒数第 k个数，即最大的第 k个数
    }
	// 堆化
    void heapify(vector<int>& vec, int n, int i) {
        int maxn = i, l = 2*i+1, r = 2*i+2;
        if(l<n && vec[l]>vec[maxn])
            maxn = l;
        if(r<n && vec[r]>vec[maxn])
            maxn = r;
        if(i != maxn) {
            swap(vec[i], vec[maxn]);
            heapify(vec, n, maxn);
        }
    }
	// 建立大顶堆
    void buildHeap(vector<int>& vec, int n) {
        for(int i=n/2-1; i>=0; i--)
            heapify(vec, n, i);
    }

二、快速选择 Quick Select

Quick Select 脱胎于快排（Quick Sort），两个算法的作者都是Hoare，并且思想也非常接近：选取一个基准元素pivot，将数组切分（partition）为两个子数组，比pivot大的扔左子数组，比pivot小的扔右子数组，然后递推地切分子数组。Quick Select不同于Quick Sort的是其没有对每个子数组做切分，而是对目标子数组做切分。其次，Quick Select与Quick Sort一样，是一个不稳定的算法；pivot选取直接影响了算法的好坏，worst case下的时间复杂度达到了O(n2)

Quick Sort 的 C++实现：

// 划分函数
int partition(vector<int>& vec, int left, int right) {
    // 取最后一个元素为标杆
    int index = left;
    while(left < right) {
        if(vec[left] < vec[right]) {
            swap(vec[left], vec[index]);
            index ++;
        }
        left++;
    }
    swap(vec[index], vec[right]);   
    return index;
}

// 快速排序
void quicksort(vector<int>& vec, int left, int right) {
    if(left >= right)    return ;

    int patitionIndex = partition(vec, left, right);
    quicksort(vec, left, patitionIndex-1);
    quicksort(vec, patitionIndex+1, right);
}

Quick Select的目标是找出第k大元素，所以:

• 若切分后的左子数组的长度 > k，则第k大元素必出现在左子数组中；
• 若切分后的左子数组的长度 = k，则第k大元素为pivot；
• 若上述两个条件均不满足，则第k大元素必出现在右子数组中。

Quick Select的C++实现如下：

		// 随机划分函数
		int randomPartition(vector<int>& vec, int left, int right) {
		  int i = rand()%(right-left+1)+left;
		  swap(vec[i], vec[right]);
		
		  return partition(vec, left, right);
		}
		
		// 快速选择
		int quickSelect(vector<int>& vec, int left, int right, int index) { 
		  int q = partition(vec, left, right);		// 取一个随机划分点
		
		  if (q == index) {								// 如果随机划分点等于 index，则返回 vec[q]
		      return vec[q];
		  } else {								// 否则，q<index说明在(q+1,right)之间，q>index在 (left, q-1)之间，不断递归下去即可找到
		      return q<index ? quickSelect(vec, q+1, right, index) : quickSelect(vec, left, q-1, index);  
		  }
		}
		
		int findKthLargest(vector<int>& nums, int k) {
		  srand(time(0));	// srand()给rand()提供随机数种子seed。
		  
		  return quickSelect(nums, 0, nums.size()-1, nums.size()-k);
		}

时间复杂度：O(n） 空间复杂度：O(logn)