k-th smallest 问题总结

发布时间：2020-12-14 03:50:55 所属栏目：大数据来源：网络整理

导读：k-th smallest/biggest 问题大约有这几道： 373. Find K Pairs with Smallest Sums 从两个list里各取一个数求和，求所有可能的sum里第k小的 378. Kth Smallest Element in a Sorted Matrix 给一个每一横排/每一纵列都有序的matrix，求其中第k小的元素 668. K

k-th smallest/biggest 问题大约有这几道：

373. Find K Pairs with Smallest Sums	从两个list里各取一个数求和，求所有可能的sum里第k小的
378. Kth Smallest Element in a Sorted Matrix	给一个每一横排/每一纵列都有序的matrix，求其中第k小的元素
668. Kth Smallest Number in Multiplication Table	给一个乘法表（类似378的matrix），求其中第k小的元素
719. Find K-th Smallest Pair Distance	从一个list里取两个元素求和，求所有可能的sum里第k小的
786. K-th Smallest Prime Fraction	从一个list里取两个元素相除，求所有可能的sum里第k小的

可以看出，其实373 719 786是同一题，378 668是同一题

这种题大致有两种思路：

1. 用heap

关于堆的介绍网上有一大把......这里只划重点

堆是一种是一种特殊的完全二叉树，其中每个根节点一定比它的左、右儿子节点都大/小（大根堆or小根堆）。每次增/删元素时，需要移动二叉树节点来保持这一性质。

时间复杂度：

从一个长度为N的乱序数组建堆? O(NlogN)

向长度为N的堆插入/删除一个元素? O(logN)

实现：

C++里可以用priority_queue<int> pq。常用操作有push(),pop(),top(),empty(),size()

Python 里可以用import heapq，然后heapq.heapify(list_a)就在原list上建好堆啦，a[0]就是堆顶。不过它只能建大根堆??

 1 import heapq
 2 
 3 #heapq implemented min heap only. Thus we save -nums[i] into the heap
 4 class Solution:
 5     def maxSlidingWindow(self,nums,k):
 6         """
 7         :type nums: List[int]
 8         :type k: int
 9         :rtype: List[int]
10         """
11         a=[]
12         res=[]
13         for i in range(len(nums)):
14             a.append(-nums[i])
15             if(i>=k):
16                 a.remove(-nums[i-k])
17             heapq.heapify(a)
18             if(i>=k-1):
19                 res.append(-a[0])
20         return res
21 
22 sl=Solution()
23 nn=[1,3,-1,-3,5,6,7]
24 rr=sl.maxSlidingWindow(nn,3)
25 print(rr)

Python的implementation实例（LeetCode 239的弱鸡解法）

解题思路：

把所有要比较的东西都塞到heap里，最后做k次取堆顶--弹出堆顶的操作

时间复杂度是 O(N^2 * log(N^2)) 有些medium题能过，但hard题肯定不行

根据题目具体情况，一开始不一定所有的东西都要塞进heap

例题：

373. Find K Pairs with Smallest Sums

反正过是能过...它的加强版就是719 786啦

priority_queue默认是大根堆，要是想要小根堆需要自定义比较函数。这里我直接重载了运算符（因为是pair嘛），推荐一下这种写法（骄傲

 1 class Solution {
 2 public:
 3     struct Node
 4     {
 5         pair<int,int> val;
 6         Node(int x,int y) {val=pair<int,int>(x,y);}
 7         bool operator <(Node a) const {return(val.first+val.second < a.val.first+a.val.second);}
 8         bool operator >(Node a) const {return(val.first+val.second > a.val.first+a.val.second);}
 9     };
10 
11     vector<pair<int,int>> kSmallestPairs(vector<int>& nums1,vector<int>& nums2,int k) 
12     {
13         vector< pair<int,int> > ans;
14         int lx=nums1.size(),ly=nums2.size();
15         if(lx==0 || ly==0) return ans;
16         k=min(k,lx*ly);
17         priority_queue<Node,vector<Node>,greater<Node> > pq;
18         for(int i=0;i<min(lx,k);i++)
19             for(int j=0;j<min(ly,k);j++)
20             {
21                 pq.push(Node(nums1[i],nums2[j]));
22             }
23 
24         while(k)
25         {
26             ans.push_back(pq.top().val);
27             pq.pop();
28             k--;
29         }
30         return ans;
31 
32     }
33 };

View Code

378. Kth Smallest Element in a Sorted Matrix

赤果果的heap。又不是不能用......

 1 //O(N*N*log(N*N))
 2 class Solution {
 3 public:
 4     int kthSmallest(vector<vector<int>>& matrix,int k)
 5     {
 6         int dx=matrix.size(),dy=matrix[0].size();
 7         priority_queue<int> pq;
 8         for(int i=0;i<dx;i++)
 9             for(int j=0;j<dy;j++)
10                 pq.push(matrix[i][j]);
11 
12         int ans;
13         k=dx*dy-k+1;
14         while(k)
15         {
16             ans=pq.top();
17             pq.pop();
18             k--;
19         }
20         return ans;
21     }
22 };

View Code

另外三题heap都是妥妥超时的噢......hard就是hard

2. Binary Search

二分查找模板了解一下：

under_construction

时间复杂度：

O(log(N))

解题思路：

用二分查找(有left,right,mid)来枚举第k小的值，然后看原数组里当前有多少是小于mid的，多了就减小right，少了就增大left。直到查找结束，此时left就是第k小值啦

实现时先对原数组按行/列排个序，或者题目本身就是保证有序的

时间复杂度是 O(log(X)*N) ，其中log(X)是二分查找的开销(X=right-left)，N是在原数组里找小于mid的数的开销（二维数组的话最坏情况可能会N^2，不过一般也能过）

例题：

378. Kth Smallest Element in a Sorted Matrix

就按上面的方法实现哒

在原数组里count时用了一个函数upper_bound(matrix[i].begin(),matrix[i].end(),mid)，返回matrix[i]这个从小到大有序的vector里小于等于mid的第一个数的指针

这玩意底层是二分查找，时间复杂度是logN呢。

 1 //O(N*log(N)*log(max-min))
 2 //Binary Search
 3 class Solution {
 4 public:
 5     int kthSmallest(vector<vector<int>>& matrix,int k)
 6     {
 7         int dx=matrix.size(),dy=matrix[0].size();
 8         int ml=matrix[0][0],mr=matrix[dx-1][dy-1];
 9         int mid,cnt;
10         while(ml<mr)
11         {
12             mid=(ml+mr)/2;
13             cnt=0;
14             for(int i=0;i<dx;i++)
15             {
16                 cnt+=upper_bound(matrix[i].begin(),mid)-matrix[i].begin();
17             }
18             if(cnt>=k)
19                 mr=mid;
20             else if(cnt<k)
21                 ml=mid+1;
22         }
23         return ml;
24     }
25 };

View Code

668. Kth Smallest Number in Multiplication Table

上面的改巴改巴就行了......

 1 //Binary Search
 2 class Solution {
 3 public:
 4     //int kthSmallest(vector<vector<int>>& matrix,int k)
 5     int findKthNumber(int m,int n,int k) 
 6     {
 7         int ml=1,mr=m*n;
 8         int mid,cnt;
 9         while(ml<mr)
10         {
11             mid=(ml+mr)/2;
12             cnt=0;
13             for(int i=1;i<=m;i++)
14             {
15                 cnt+=min(mid/i,n);
16             }
17             if(cnt>=k)
18                 mr=mid;
19             else if(cnt<k)
20                 ml=mid+1;
21         }
22         return ml;
23     }
24 };

View Code

719. Find K-th Smallest Pair Distance

一样的套路噢...就是从一个matrix变成了两个list

 1 // Binary Search
 2 class Solution {
 3 public:
 4     int smallestDistancePair(vector<int>& nums,int k)
 5     {
 6         int n=nums.size();
 7         sort(nums.begin(),nums.end());
 8         int ml=nums[1]-nums[0],mr=nums[n-1]-nums[0],mid=0,cnt=0;
 9         for(int i=0;i<n-1;i++) ml=min(ml,nums[i+1]-nums[i]);
10         while(ml<mr)
11         {
12             mid=(ml+mr)/2;
13             cnt=0;
14             for(int i=0;i<n;i++)
15             {
16                 int j=i+1;
17                 while(j<n && nums[j]-nums[i]<=mid) j++;
18                 cnt+=(j-i-1);
19             }
20             if(cnt<k)
21                 ml=mid+1;
22             else
23                 mr=mid;
24         }
25         return ml;
26     }
27 };

View Code

这题其实还有个骚操作：因为list值的范围比较小，所以可以用counting sort：先用O(N^2)的时间把所有可能的pair和记下来，然后在counting sort的数组里从小到大数数即可

不过感觉这方法通用性应该不强...

 1 //counting sort: O(N^2)
 2 class Solution {
 3 public:
 4     int smallestDistancePair(vector<int>& nums,int k) 
 5     {
 6         int val[1000010];
 7         memset(val,0,sizeof(val));
 8         int nl=nums.size();
 9         for(int i=0;i<nl;i++)
10             for(int j=i+1;j<nl;j++)
11             {
12                 //cout<<abs(nums[j]-nums[i])<<endl;
13                 val[abs(nums[j]-nums[i])]++;
14             }
15 
16         int ans=0;
17         while(k)
18         {
19             if(val[ans]>0) 
20             {
21                 //cout<<k<<" "<<ans<<endl;
22                 val[ans]--;
23                 k--;
24             }
25             else ans++;
26         }
27         return ans;
28     }
29 };

View Code

786. K-th Smallest Prime Fraction

这题坑多一点，因为是分数，涉及到浮点数嘛

涉及到浮点数就不能直接用=比较辣，要用r-l<eps。

以及注意两个int做除法，要先强制转换成double

 1 //Binary Search,AC
 2 class Solution {
 3 public:
 4     vector<int> kthSmallestPrimeFraction(vector<int>& A,int k) 
 5     {
 6         vector<int> ans;
 7         int al=A.size();
 8         sort(A.begin(),A.end());
 9         double ml=0.0,mr=1.0,md=0.5;
10         int dx,dy,cnt;
11         double eps=1e-10;
12         while(mr-ml>eps)
13         {
14             md=(ml+mr)/2;
15             cnt=0;
16             for(int i=0;i<al;i++)
17             {
18                 int j=al-1;
19                 while(j>i && (double)A[i]/(double)A[j]<md) j--;
20                 cnt+=(al-1-j);
21             }
22             cout<<ml<<","<<mr<<"=="<<md<<" "<<cnt<<endl;
23             if(cnt<k)
24                 ml=md;
25             else
26                 mr=md;
27             
28         }
29         for(int i=0;i<al;i++)
30             for(int j=i+1;j<al;j++)
31                 if(abs((double)A[i]/(double)A[j] - ml)<eps)
32                 {
33                     dx=A[i]; dy=A[j];
34                     ans.push_back(dx); ans.push_back(dy);
35                     return(ans);
36                 }
37         return ans;
38     }
39 };

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!