杨氏矩阵找第N大(小)的O(N)线性算法 LeetCode 378. Kth Smallest Element in a Sorted Matrix 373. Find K Pairs 钓鱼问题

杨氏矩阵一个N*N的矩阵它的每行每列都单调递增(或者宽松一些,单调不减)即a[i][j]a[i1][j], a[i][j]a[i][j1]。遇到的两道面试题1. 输出杨氏矩阵中最小的N个数。2. 两个升序数组A和B长度都是N。从两个数组中分别取出一个数相加得到一个和。求这N*N个和的前N小。本质上第2题可以转化成第一题把A[0]B[k]的结果填入矩阵第一行A[1]B[k]的结果填入第二行……就得到一个杨氏矩阵。所以现在就只考虑第1题咯。此题常见的一种做法N路归并用一个大小为N的堆可以O(NlgN)得到解。但是利用杨氏矩阵的性质这题是有O(N)的算法的……为了方便把矩阵记为num首先根据杨氏矩阵的性质得到最关键的一点前N小的数肯定不大于矩阵中的num[sqrt(N)1][sqrt(N)1]。为了方便令M sqrt(N)1因此要找的前N小的数肯定在矩阵的前M行和前M列中。所以要找的是一个M*N的矩阵和另外一个(N-M)*M的矩阵。这样的规模相当于M*(2N-M)相当于M*N这样问题可以转化为在M个长度为N的有序数组中查找前N小的数。(*)除了之前提到的方法此题还有一个比较容易想到的方法二分上界并计数。在INT_MIN~INT_MAX中二分第K大数的上界每次对所有数组二分统计其中不大于上界的数的个数。总体的复杂度是O(R*M*lgN)。其中R是最坏情况下二分的次数。对于32位整数最多二分32次R32。但是对于浮点数需要的二分次数会增多。在这个思路的基础上加以改进把R改进为lgN便可得到线性算法。基本思路是把二分时取数的范围从INT_MIN~INT_MAX缩小到这MN个数中。每次从这些数中选一个来作为计数的上界。选的方法每一轮计数时先找出这M个数组的中位数作为每个数组潜在的切分点然后选择这些切分点的中位数作为上界。O(M)选出M个切分点O(MlgM把这些数排个序再选中间的所以这一步可以O(MlgM)注无序数组选中位数有均摊O(M)的算法。但是为了每一轮都能缩小查找范围所以对于每个数组还要维护一个“潜在切分点的可能区间”选择该数组的新切分点时取这个区间的中位数。实际上就是对每个数组维护一个二分切分点的过程信息。这样一轮统计过后某些偏大或偏小的切分点所在区间长度就需要减半。并且至少有半数区间的长度是要减半的。对于一个数组不大于中位数的数的个数至少是一半。“不小于”同理由于所有数组一共有MN个数因此在lg(MN)轮后所有区间长度都会减到1。整理一下复杂度。一共要进行lg(MN)次计数每次计数需要O(MlgM)找切分点的中位数以及O(MlgN)对一个数组计数。因此整体的复杂度是O(lg(MN)*(MlgMMlgN)) O(sqrt(N)*(lgN)^2) o(sqrt(N)*sqrt(N)) o(N)ps. 所以这个算法复杂度其实是低于O(N)的.(*)附代码用以上算法实现在M个有序数组中查找第K小的数。转自http://wolf5x.cc/blog/algorithm/young-tableau-smallest-kth#comment-123#include iostream #include vector #include algorithm using namespace std; // i, partition_point_lower_index_i, partition_point_upper_index_i typedef pairint, pairint,int PartRange; typedef vectorvectorint VVI; class PartComparator { const VVI ary; public: PartComparator(const VVI a): ary(a){} bool operator()(const PartRange x, const PartRange y) const { return ary[x.first][(x.second.firstx.second.second)/2] ary[y.first][(y.second.firsty.second.second)/2]; } }; // Get the count of numbers less than or equal to upper int getCount(VVI num, int upper) { int ret 0; for (int i 0; i num.size(); i) { ret upper_bound(num[i].begin(), num[i].end(), upper) - num[i].begin(); } return ret; } int chooseKthSmallest(VVI num, int k) { int n num.size(); vectorPartRange part(n); for (int i 0; i n; i) { part[i] make_pair(i, make_pair(0, num[i].size()-1)); } int ans 130; // INT_MAX; while(part.size() 0) { // sort all the medians sort(part.begin(), part.end(), PartComparator(num)); // choose the median of medians int mid part.size()/2; int upper num[part[mid].first][(part[mid].second.firstpart[mid].second.second)/2]; int count getCount(num, upper); if (count k) { // update answer ans min(ans, upper); // halve the median intervals of which the median is too large for(int i 0; i part.size(); i) { int mid (part[i].second.firstpart[i].second.second)/2; if (num[part[i].first][mid] upper) { part[i].second.second mid-1; } } } else { // halve the median intervals of which the median is too small for (int i 0; i part.size(); i) { int mid (part[i].second.firstpart[i].second.second)/2; if (num[part[i].first][mid] upper) { part[i].second.first mid1; } } } // remove the empty median intervals for (int i part.size()-1; i 0; i--) { if (part[i].second.first part[i].second.second) { swap(part[i], part[part.size()-1]); part.erase(part.end()-1); } } } return ans; } int main() { int v[][3] {{1,2,3},{2,3,4},{3,4,5}}; vectorint vec0(v[0],v[0]3); vectorint vec1(v[1],v[1]3); vectorint vec2(v[2],v[2]3); int arr[] {1,2,2,3,4,4,4,4,5,6,7,8,9,9,10}; vectorint vec3(arr, arrsizeof(arr)/sizeof(int)); VVI num; num.push_back(vec0); num.push_back(vec1); num.push_back(vec2); int up distance(vec3.begin(), upper_bound(vec3.begin(), vec3.end(), 11)); int low distance(vec3.begin(), lower_bound(vec3.begin(), vec3.end(), 11)); int res chooseKthSmallest(num, 3); return 0; }--------------------------------------------------------------------------------------------------------很久之后发现一种更好的解法仍然二分假设数据二分的范围是整个整数那么log(2^32)次最多是32次实际中范围可以由左上角和右下角来确定anyway二分的次数可以看做是一个常数。。。剩下的问题就是给定一个target求这个matrix中target的元素个数这个是可以O(n)实现的也就是从右上角开始往下找。。所以整体复杂度是O(n)。LeetCode上恰好有这么一道题Given anxnmatrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the kth distinct element.Example:matrix [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k 8, return 13.Note:You may assume k is always valid, 1 ≤ k ≤ n2.-----------------------------------------------------------class Solution: def count_lower(self, nums, target, n): j, res n - 1, 0 for i in range(n): while (j 0 and nums[i][j] target): j - 1 res (j 1) return res def kthSmallest(self, matrix, k: int) - int: n len(matrix) left, right matrix[0][0], matrix[n - 1][n - 1] while (left right): target ((right - left) 1) left lower self.count_lower(matrix, target, n) if (lower k): left target 1 else: right target - 1 return left------------------------------------------------另外一道题要求输出也排序就只能用堆来玩了You are given two integer arraysnums1andnums2sorted inascending orderand an integerk.Define a pair(u, v)which consists of one element from the first array and one element from the second array.Returnthekpairs(u1, v1), (u2, v2), ..., (uk, vk)with the smallest sums.Example 1:Input:nums1 [1,7,11], nums2 [2,4,6], k 3Output:[[1,2],[1,4],[1,6]]Explanation: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:Input:nums1 [1,1,2], nums2 [1,2,3], k 2Output:[[1,1],[1,1]]Explanation: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:Input:nums1 [1,2], nums2 [3], k 3Output:[[1,3],[2,3]]Explanation:All possible pairs are returned from the sequence: [1,3],[2,3]Constraints:1 nums1.length, nums2.length 105-109 nums1[i], nums2[i] 109nums1andnums2both are sorted inascending order.1 k 1000from typing import List import heapq class Solution: def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) - List[List[int]]: l1, l2 len(nums1), len(nums2) hq,res [(nums1[0]nums2[0],0,0)],[] while (hq and len(res) k): csum,i,j heapq.heappop(hq) res.append([nums1[i],nums2[j]]) if (j1l2): heapq.heappush(hq,(nums1[i]nums2[j1],i,j1)) #列维度扩张由j说了算只有列是0的时候考虑一下行维度的扩张也控制了优先级 if j 0 and i1l1: heapq.heappush(hq,(nums1[i1]nums2[j],i1,j)) return res s Solution() print(s.kSmallestPairs(nums1 [1,2], nums2 [3], k 3)) print(s.kSmallestPairs(nums1 [1,1,2], nums2 [1,2,3], k 2)) print(s.kSmallestPairs(nums1 [1,7,11], nums2 [2,4,6], k 3)) #expected: [[0, -3], [0, -3], [0, -3], [0, -3], [0, -3], [0, 22], [0, 22], [0, 22], [0, 22], [0, 22], [0, 35], [0, 35], [0, 35], [0, 35], [0, 35], [0, 56], [0, 56], [0, 56], [0, 56], [0, 56], [0, 76], [0, 76]] # [[0, -3], [0, 22], [0, 35], [0, 56], [0, 76], [0, -3], [0, 22], [0, 35], [0, 56], [0, 76], [0, -3], [0, 22], [0, 35], [0, 56], [0, 76], [0, -3], [0, 22], [0, 35], [0, 56], [0, 76], [0, -3], [0, 22]] # [[0, -3], [0, -3], [0, -3], [0, -3], [0, -3], [0, 22], [0, 22], [0, 22], [0, 22], [0, 22], [0, 35], [0, 35], [0, 35], [0, 35], [0, 35], [0, 56], [0, 56], [0, 56], [0, 56], [0, 56], [0, 76], [0, 76]] print(s.kSmallestPairs([0,0,0,0,0],[-3,22,35,56,76],22))------------------------------------------------又发现一道钓鱼问题有n个湖在一条路上每个湖产量不一样A[n]均为正整数。​每个湖被钓1个小时之后产量会减1再被钓1小时后产量再减1没被钓不降低产量。​有k个小时求最大钓鱼量:解答这个题也很容易想到用堆的思路但是比较好的思路是假设产量超过x的湖才会钓鱼然后二分就可以得到O(n)复杂度解法。------------------------------------------------一组排序质数任选两个组成真分数求所有可能中第k小。请给出复杂度最小的做法class Solution: def count_lower(self, arr, target, n): i, res, p, q 0, 0, arr[0], arr[n - 1] for j in range(1, n): while (i j and arr[i] target * arr[j]): i 1 res i if (i 0 and arr[i - 1] * q p * arr[j]): p, q arr[i - 1], arr[j] return res, p, q def kthSmallest(self, arr, k): n len(arr) total n * (n - 1) // 2 if (k 1 or k total): raise ValueError(fk{k} out of range [1, {total}]) left, right, ans 0.0, 1.0, [arr[0], arr[n - 1]] while (right - left 1e-9): target (left right) / 2 lower, p, q self.count_lower(arr, target, n) if (lower k): left target else: right target ans [p, q] return ans