1、leetcode 215. Kth Largest Element in an Array 剑指offer 40最小的k个数

题意：在一个未排序数组中找到第K大的数并输出

（1）排序之后直接输出倒数第K个数 

时间复杂度O（nlogn），空间复杂度O(1)

public int findKthLargest(int[] nums, int k) { final int N = nums.length; Arrays.sort(nums); return nums[N - k]; }

（2）使用小顶堆，遍历一遍之后，输出堆顶 剑指offer里面使用的是set 红黑树

时间复杂度O（nlogk），空间复杂度O(1)，时间复杂度降低，空间复杂度下降

注意，priority_queue<int>默认是大顶堆，需要使用priority_queue<int,vector<int>,greater<int>>

class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int,vector<int>,greater<int>> q; for(int i=0;i<nums.size();i++) { if(i<k) q.push(nums[i]); else { if(nums[i]>q.top()) { q.pop(); q.push(nums[i]); } } } return q.top(); } }; 另外一种：

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

（3）基于partition方法

最好是O(N) ，最差是O(N^2) ，空间O(1)

思路：基于快排的思想，不同是，快排每次选择一个数作为pivot，这里不需要把所有的数都排玩，当pivot的标号正好是第k个位置时，就可以停止了。

class Solution { public: int findKthLargest(vector<int>& nums, int k) { int n=nums.size(); int aim=n-k; int left=0; int right=n-1; while(left<right) { int pivot=partition(nums,left,right); if(pivot>aim) { right=pivot-1; } else if(pivot<aim) left=pivot+1; else break; } return nums[aim]; } int partition(vector<int>& nums,int left,int right){//这里的partition方法非常简洁 int i=left; int j=right+1; while(true) { while(i<right&&nums[++i]<nums[left]);//从左到右找到第一个大于标签值的数 while(j>left&&nums[--j]>nums[left]);//从右到左找到第一个小于标签值的数 if(i>=j)//有可能两个指针已经交叉了，先做这个判断 break; swap(nums[i],nums[j]);//两个指针没有交叉right指向的数一定小于pivot } swap(nums[left],nums[j]); return j; } };

（4）O(N)时间复杂度，O(1)空间复杂度 随机打乱原来的数组，使得基本有序的情况尽量少

public int findKthLargest(int[] nums, int k) { shuffle(nums); k = nums.length - k; int lo = 0; int hi = nums.length - 1; while (lo < hi) { final int j = partition(nums, lo, hi); if(j < k) { lo = j + 1; } else if (j > k) { hi = j - 1; } else { break; } } return nums[k]; } private void shuffle(int a[]) { final Random random = new Random(); for(int ind = 1; ind < a.length; ind++) { final int r = random.nextInt(ind + 1); exch(a, ind, r); } }

（5）BFPRT算法  O(N)时间复杂度

2 378. Kth Smallest Element in a Sorted Matrix

在排序矩阵（行列递增序，不是整体递增）中找到最小的第k个数 我的思路： 看反斜杠，左上角的反斜杠，前一排的数整体小于后一排，找到第k个数所在的反斜杠， 前面的数共有n个，针对目前的反斜杠建立一个k-n的最大堆。 （1）思路1： 堆  这个题目涉及到类和优先级队列的扩展使用 把第一行建立成一个堆，然后做k次以下操做： 把当前堆中最小的数弹出，同时，保存弹出数据的下一列对应的数。重复k次 这种方法保证每次弹出的都是第i小的数,当第k次弹出时就是第k小的数。 算法复杂度n+klongk class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { priority_queue<number,vector<number>,cmp> q; int n=matrix.size(); int m=matrix[0].size(); for(int i=0;i<m;i++) { q.push({matrix[0][i],0,i}); } number res; for(int j=0;j<k;j++) { res=q.top(); q.pop(); if(res.ro==n-1) continue; int num=matrix[res.ro+1][res.col]; q.push({num,res.ro+1,res.col}); } return res.num; } struct number{ int num; int ro;//行 int col;//列 }; struct cmp{ bool operator()(const number& a,const number& b){ return a.num>b.num; } }; };另一个版本，使用pair make_pair class Solution { public: struct compare { bool operator()(const pair<int,pair<int, int> >& a, const pair<int,pair<int, int> >& b) { return a.first>b.first; } }; int kthSmallest(vector<vector<int>>& arr, int k) { int n=arr.size(),m=arr[0].size(); priority_queue< pair<int,pair<int, int> >, vector<pair<int, pair<int, int> > >, compare > p; for(int i=0;i<n;i++) p.push(make_pair(arr[i][0],make_pair(i,0))); int x=k,ans; while(x--) { int e=p.top().first; int i=p.top().second.first; int j=p.top().second.second; ans=e; p.pop(); if(j!=m-1) p.push(make_pair(arr[i][j+1],make_pair(i,j+1))); } return ans; } }; （2）思路2： 使用二分法。n*nlogn 找到最小值和最大值的中位数，统计所有数中比这个数小的个数，如果小于k说明，第k个数在右边，否则在左边。

373. Find K Pairs with Smallest Sums

与上题类似

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Return: [1,2],[1,4],[1,6] The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Return: [1,1],[1,1] The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Given nums1 = [1,2], nums2 = [3], k = 3 Return: [1,3],[2,3] All possible pairs are returned from the sequence: [1,3],[2,3] class Solution { public: vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { priority_queue<pair<int,pair<int,int>>> q; vector<pair<int,int>> res; for(int i=0;i<nums1.size();i++) for(int j=0;j<nums2.size();j++) { if(k>0)//初始k还没有构造完成 { q.push(make_pair(nums1[i]+nums2[j],make_pair(nums1[i],nums2[j]))); k--; } else if(nums1[i]+nums2[j]<q.top().first) { q.pop(); q.push(make_pair(nums1[i]+nums2[j],make_pair(nums1[i],nums2[j]))); } } while(!q.empty()) { res.push_back(make_pair(q.top().second.first,q.top().second.second)); q.pop(); } return vector<pair<int,int>>(res.rbegin(),res.rend()); } struct cmp{ bool operator()(const pair<int,pair<int,int>>& a,const pair<int,pair<int,int>>& b ){ return a.first<b.first; } }; };另外一个，方法一样，使用lambda表达式，priority_queue和vector都有emplace函数，写入新的元素时，可以直接传递构成参数。 但是这个方法比上一个要好的多，因为两个数组都是排好序的，所以每次加到有限级队列的数应该只能是两个数组的下一个，这样能够保证每次弹出的数一定是所有序列中最小的第i个，这样，只需要循环k次。 class Solution { public: vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { vector<pair<int,int>> result; if (nums1.empty() || nums2.empty() || k <= 0) return result; auto comp = [&nums1, &nums2](pair<int, int> a, pair<int, int> b) { return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];}; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> min_heap(comp); min_heap.emplace(0, 0); while(k-- > 0 && min_heap.size()) { auto idx_pair = min_heap.top(); min_heap.pop(); result.emplace_back(nums1[idx_pair.first], nums2[idx_pair.second]); if (idx_pair.first + 1 < nums1.size()) min_heap.emplace(idx_pair.first + 1, idx_pair.second); if (idx_pair.first == 0 && idx_pair.second + 1 < nums2.size()) min_heap.emplace(idx_pair.first, idx_pair.second + 1); } return result; } };

668. Kth Smallest Number in Multiplication Table

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 3 6 9 The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6). 在乘法表中寻找第k个数 class Solution { public:     int findKthNumber(int m, int n, int k) {         int lo=1;         int high=m*n+1;         while(lo<high)         {             int mid=lo+(high-lo)/2;//找中间数             int c=count(m,n,mid);//统计所有不大于mid的数             if(c>=k) high=mid;//如果c==k不能保证mid就是要找的数，因为可能mid并不在数组内             else lo=mid+1;         }         return high;     }     int count(int m,int n,int t){//寻找t所在的位置         int res=0;         for(int i=1;i<=m;i++)         {             res+=min(t/i,n);//t/i是对应的列值，如果这个数大于n(列最大)，说明这一行所有的数都比t小。通过循环，把所有小于等于t的数都统计出来         }         return res;     } };