215.KthLargestElementinanArray.md

找数组里第K大元素（随机选择、堆）

1. 来源：
   • 力扣215. Kth Largest Element in an Array
   • 领扣5. 第k大元素
2. 方法：利用快排的思路（但不需递归）。
   • 对于size为N的升序数组，第K小的元素下标是K-1，第K大的元素下标就是N-K。
   • 回顾快排：
     • 每次选择pivot。可以选最左边，或者随机选。（时间复杂度优化1）
     • 比它小的元素都在左边，比它大的都在右边，
     • 使得值为pivot的元素归位。（即是它在排好序数组里的最终位置。）
   • 利用快排思路解决本题
     • 由于快排具有每次归位一个元素的优点，
     • 利用这一点，我们记下这个已归位的元素的位置，使得查找区间控制在N-K附近（优化2）
     • 这个有点像二分查找？
   • 具体操作如下：
     • 每次返回pivot的位置index：
     • 如果index在N-K左边，那么，让left=index+1；否则，让right=index-1
     • 如果index刚好等于N-K。直接返回结果！
3. 实现：迭代版本

• 一，每次选择最左边元素为pivot

  class Solution {
  public:
      // 根据快排改写。
      int QuickSelect(vector<int> &A, int l, int r)
      {
          // if(l>r)
          //     return;    
          
          int pivot = A[l], i=l, j=r;
          
          while(i<j)
          {
              while(A[j]>=pivot && i<j) j--;
              while(A[i]<=pivot && i<j) i++;
              if(i<j)
                  swap(A[i], A[j]);
          }
          
          swap(A[i], A[l]); //pivot归位
          // quick_sort(A, l, i-1);
          // quick_sort(A, i+1, r);
          
          return i;
      }
      
      int findKthLargest(vector<int> &nums, int k) {
          int index, left=0, right=nums.size()-1;
          int n = nums.size();
          while(left<right)
          {
              index = QuickSelect(nums, left, right);
              if(index==n-k)
                  break;
              else if(index > n-k)    right = index-1;            
              else    left = index+1;
          
          }
          return nums[n-k];
          // write your code here
      }
  };
  

• 二，随机选择pivot

  class Solution {
  public:
      // 根据快排改写。
      int QuickSelect(vector<int> &A, int l, int r)
      {
          /*
          if(l>r)
               return; 
          */   
          int pos = rand()%(r-l+1) + l;   // 生成【l,r】之间随机整数
          int pivot = A[pos];
          //始终将第一个元素作为pivot, 若不是, 则与之交换
          if (pos != l) {
              swap(A[l], A[pos]);
          }
          
          int i=l, j=r;            
          while(i<j)
          {
              while(A[j]>=pivot && i<j) j--;
              while(A[i]<=pivot && i<j) i++;
              if(i<j)
                  swap(A[i], A[j]);
          }
          
          swap(A[i], A[l]); //pivot归位
          /*
          quick_sort(A, l, i-1);
          quick_sort(A, i+1, r);
          */
          
          return i;
      }
      
      int findKthLargest(vector<int> &nums, int k) {
          srand((unsigned)time(NULL));
          int index, left=0, right=nums.size()-1;
          int n = nums.size();
          while(left<right)
          {
              index = QuickSelect(nums, left, right);
              if(index==n-k)
                  break;
              else if(index > n-k)    right = index-1;            
              else    left = index+1;
          
          }
          return nums[n-k];
          // write your code here
      }
  };
  

• 三，堆/优先队列

  class Solution {
  public:
      // O(N + klogN)
      int findKthLargest(vector<int>& nums, int k) {
          priority_queue<int>max_heap(nums.begin(),nums.end());  // O(N)
          for(int i=0; i<k-1; i++)
          {
              max_heap.pop();     // O(logN)            
          }
          return max_heap.top();
      }
  };