给定两个有序数组arr1和arr2,再给定一个整数K,返回所有数中第K小的数。
[要求]
如果arr1的长度为N,arr2的长度为M,时间复杂度请达到,额外空间复杂度。
第一行三个整数N, M, K分别表示数组arr1, arr2的大小,以及需要询问的数
接下来一行N个整数,表示arr1内的元素
再接下来一行M个整数,表示arr2内的元素
输出一个整数表示答案
5 3 1 1 2 3 4 5 3 4 5
1
1是所有数中第一小的数
3 4 4 1 2 3 3 4 5 6
3
3是所有数中第4小的数,所以返回3
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]), k = Integer.parseInt(params[2]); params = br.readLine().split(" "); int[] nums1 = new int[n]; for(int i = 0; i < n; i++) nums1[i] = Integer.parseInt(params[i]); params = br.readLine().split(" "); int[] nums2 = new int[m]; for(int i = 0; i < m; i++) nums2[i] = Integer.parseInt(params[i]); // 归并 int p1 = 0, p2 = 0, p = 0; while(p1 < n && p2 < m){ if(nums1[p1] < nums2[p2]){ p1 ++; p ++; if(p == k){ System.out.println(nums1[p1 - 1]); break; } }else{ p2 ++; p ++; if(p == k){ System.out.println(nums2[p2 - 1]); break; } } } } }
#include <bits/stdc++.h> using namespace std; int findKth(vector<int> a, vector<int> b, int k) { // 总是让A的大小小于B if(a.size() > b.size()) return findKth(b, a, k); //终止条件 if(a.size() == 0) return b[k - 1]; if(k == 1) return min(a[0], b[0]); int m = a.size(); int n = b.size(); int i = min(m, k / 2); // 如果大小不足k/2,取自身大小 int j = k - i; if(a[i - 1] > b[j - 1]) return findKth(a, vector<int>(b.begin() + j, b.end()), k - j); else if(a[i - 1] < b[j - 1]) return findKth(vector<int>(a.begin() + i, a.end()), b, k - i); else return a[i-1]; } int main(){ vector<int> a,b; int a_len, b_len, k, x; cin >> a_len >> b_len >> k; for(int i = 0; i < a_len; i++){ cin >> x; a.push_back(x); } for(int j = 0; j < b_len; j++){ cin >> x; b.push_back(x); } int target = findKth(a, b, k); cout << target; return 0; }
#include <bits/stdc++.h> using namespace std; int main(){ int n, m, k, x; cin>>n>>m>>k; priority_queue<int, vector<int>, greater<int> > q; for(int i=0;i<n;i++){ cin>>x; if(i<k) q.push(x); } for(int i=0;i<m;i++){ cin>>x; if(i<k) q.push(x); } while(k-->1) q.pop(); cout<<q.top()<<endl; return 0; }
#include<bits/stdc++.h> using namespace std; int main() { int n,m,k; cin>>n>>m>>k; vector<int>arr1(n),arr2(m); multiset<int>s; for(int i=0;i<n;i++) { cin>>arr1[i]; s.insert(arr1[i]); } for(int i=0;i<m;i++) { cin>>arr2[i]; s.insert(arr2[i]); } set<int>::iterator it=s.begin(); for(int i=0;i<k-1;i++) it++; cout<<*it<<endl; return 0; }
#include <bits/stdc++.h> using namespace std; int getUpmid(vector<int> a, int s1, int e1, vector<int> b, int s2, int e2){ int mid1 = 0; int mid2 = 0; int offset = 0; while(s1 < e1){ mid1 = s1+((e1-s1)>>1); mid2 = s2+((e2-s2)>>1); offset = ((e1-s1+1)&1)^1; if(a[mid1] < b[mid2]){ s1 = mid1 + offset; e2 = mid2; }else if(a[mid1] > b[mid2]){ e1 = mid1; s2 = mid2 + offset; }else return a[mid1]; } return min(a[s1], b[s2]); } int getKth(vector<int> a, vector<int> b, int n, int m, int k){ vector<int> shorts = n < m ? a : b; vector<int> longs = n >= m ? a : b; int s = shorts.size(); int l = longs.size(); if(k <= s) return getUpmid(shorts, 0, k-1, longs, 0, k-1); if(k > l){ if(shorts[k-l-1] >= longs[l-1]) return shorts[k-l-1]; if(longs[k-s-1] >= shorts[s-1]) return longs[k-s-1]; return getUpmid(shorts, k-l, s-1, longs, k-s, l-1); } if(longs[k-s-1] >= shorts[s-1]) return longs[k-s-1]; return getUpmid(shorts, 0, s-1, longs, k-s, k-1); } int main(){ int n, m, k; scanf("%d%d%d", &n, &m, &k); vector<int> a(n), b(m); for(int i=0; i<(n+m); i++){ if(i<n) scanf("%d", &a[i]); else scanf("%d", &b[i-n]); } cout << getKth(a, b, n, m, k); return 0; }
# 题目要求是log的时间复杂度,利用自带的sort去排序,但是能accept # 实际上目前最好的排序方法时间复杂度为nlog2n,所以该方法实际时间复杂度不符合题意 def Tow_find_K(): n,m,k = list(map(int, input().split())) arr1 = list(map(int, input().split())) arr2 = list(map(int, input().split())) arr = arr1 + arr2 arr.sort() print(arr[k-1]) if __name__ == '__main__': Tow_find_K()
#include "iostream" #include "vector" #include "set" #include "map" #include "limits.h" #include "algorithm" using namespace std; int process(vector<int> v1,vector<int> v2,int l1,int r1,int l2,int r2) { int mid1 = (l1+r1)/2; int mid2 = (l2+r2)/2; vector<int> bigger; vector<int> smaller; int bigger_l,bigger_r; int smaller_l,smaller_r; if(v1[mid1] == v2[mid2]) return v1[mid1]; else if(v1[mid1] > v2[mid2]) { bigger.assign(v1.begin(),v1.end()); smaller.assign(v2.begin(),v2.end()); bigger_l = l1; bigger_r = r1; smaller_l = l2; smaller_r = r2; } else { bigger.assign(v2.begin(),v2.end()); smaller.assign(v1.begin(),v1.end()); bigger_l = l2; bigger_r = r2; smaller_l = l1; smaller_r = r1; } bool odd = false; if((r1-l1+1) & 0x1 == 1) odd = !odd; if(odd) { if(smaller[(smaller_l+smaller_r)/2] >= bigger[(bigger_l+bigger_r)/2-1]) return smaller[(smaller_l+smaller_r)/2]; else return process(bigger,smaller,bigger_l,(bigger_l+bigger_r)/2-1,(smaller_l+smaller_r)/2+1,smaller_r); } else { return process(bigger,smaller,bigger_l,(bigger_l+bigger_r)/2,(smaller_l+smaller_r)/2+1,smaller_r); } } int findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2,int k) { vector<int> shortv; vector<int> longv; shortv = nums1.size() < nums2.size() ? nums1 : nums2; longv = nums1.size() >= nums2.size() ? nums1 : nums2; if( k <=shortv.size()) { return process(shortv,longv,0,k-1,0,k-1);//1<=k<=短的长度 取k个数求上中位数 } else if(k > shortv.size() && k <= longv.size())//短的长度<=k<=长的长度 短的都能取到 长的取长-k - k长度 { if(longv[k-shortv.size()-1] >= shortv[shortv.size()-1])//发现长的多一个,手动比较一下 return longv[k-shortv.size()-1]; else return process(shortv,longv,0,shortv.size()-1,k-shortv.size(),k-1); } else if(k > longv.size() && k <= shortv.size()+longv.size()) //k>长的长度 短的:k-长长度-最后有可能 长的:k - 短长度-最后有可能 { //算出上中位数发现少了一个,那还有手动排除两个 if(longv[k-shortv.size()-1] >= shortv[shortv.size()-1]) return longv[k-shortv.size()-1]; else if( shortv[k-longv.size()-1] >= longv[longv.size()-1]) return shortv[k-longv.size()-1]; else return process(shortv,longv,k-longv.size(),shortv.size()-1,k-shortv.size(),longv.size()-1); } } //已知长度的输入 int main() { int n,m,k; cin>>n>>m>>k; int in; vector<int> v1; vector<int> v2; while(n > 0) { cin>>in; v1.push_back(in); n--; } while(m > 0) { cin>>in; v2.push_back(in); m--; } cout<<findMedianSortedArrays(v1,v2,k)<<endl; return 0; }