免费建企业网站哪个好,计算机前景和就业,wordpress转盘抽奖源码,wechat官方下载给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)#xff0c;其中第一个元素来自 nums1#xff0c;第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1: 输入: nums1 [1,7,11], nums2 …给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)其中第一个元素来自 nums1第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1: 输入: nums1 [1,7,11], nums2 [2,4,6], k 3 输出: [1,2],[1,4],[1,6] 解释: 返回序列中的前 3 对数 [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2: 输入: nums1 [1,1,2], nums2 [1,2,3], k 2 输出: [1,1],[1,1] 解释: 返回序列中的前 2 对数 [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3] 二分
class Solution {
public:vectorvectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) {int m nums1.size();int n nums2.size();auto count [](int target){int start 0;int end n - 1;long long cnt 0;while(start m end 0){if(nums1[start] nums2[end] target){end--;}else{cnt end 1;start;}}return cnt;};int left nums1[0] nums2[0];int right nums1[m-1] nums2[n-1];while(left right){int mid (left right) 1;if(count(mid) k){left mid 1;}else{right mid;}}vectorvectorint ans;int pos n - 1;for(int i 0; i m; i){while(pos 0 nums1[i] nums2[pos] left){pos--;}for(int j 0; j pos k 0; k--, j){ans.push_back({nums1[i], nums2[j]});}}pos n - 1;for(int i 0; i m k 0; i){int start1 i;while(i m - 1 nums1[i] nums1[i1]){i;}while(pos 0 nums1[i] nums2[pos] left){pos--;}int start2 pos;while(pos 0 nums2[pos] nums2[pos-1]){pos--;}if(nums1[i] nums2[pos] ! left){continue;}int count min((long)k, (long)(i - start1 1) * (start2 - pos 1));for(int j 0; j count k 0; j, k--){ans.push_back({nums1[i], nums2[pos]});}}return ans;}
};使用二分法实际上就是另外一种使用试探的方式。nums1[0] nums2[0]是两个数组元素和的最小值组成二分下界nums1[m-1] nums2[n-1]组成二分上界。我们使用二分查找查找出当和为多少的时候刚好是第k对数字。
我们定义一个count函数count函数的目的实际上就是计算出小于等于我们传入的mid的组合一共有多少个以便与k进行比较从而找出我们最终需要的和是多少。
最终二分查找结束left便是和第k小的元素对的和。由于我们最终要返回的是前k小的所有的数组对。那么我们在代码中首先先要找出和比left小的数组对是什么。
vectorvectorint ans;int pos n - 1;for(int i 0; i m; i){while(pos 0 nums1[i] nums2[pos] left){pos--;}for(int j 0; j pos k 0; k--, j){ans.push_back({nums1[i], nums2[j]});}}接下来我们要查找出和等于left的元素对
pos n - 1;for(int i 0; i m k 0; i){int start1 i;while(i m - 1 nums1[i] nums1[i1]){i;}while(pos 0 nums1[i] nums2[pos] left){pos--;}int start2 pos;while(pos 0 nums2[pos] nums2[pos-1]){pos--;}if(nums1[i] nums2[pos] ! left){continue;}int count min((long)k, (long)(i - start1 1) * (start2 - pos 1));for(int j 0; j count k 0; j, k--){ans.push_back({nums1[i], nums2[pos]});}}最后返回ans即是答案
