给定两个有序数组arr1和arr2,已知两个数组的长度都为N,求两个数组中所有数的上中位数。
上中位数:假设递增序列长度为n,若n为奇数,则上中位数为第n/2+1个数;否则为第n个数
[要求]
时间复杂度为,额外空间复杂度为
第一行一个整数N,表示数组大小。
接下来一行N个整数,表示arr1内的元素
再接下来一行N个整数,表示arr内的元素
输出一个整数表示答案
4 1 2 3 4 3 4 5 6
3
总共有8个数,上中位数是第4小的数,所以返回3。
3 0 1 2 3 4 5
2
总共有6个数,那么上中位数是第3小的数,所以返回2
#include <bits/stdc++.h> using namespace std; int main(){ int n, l=0, r=0, m; cin>>n; int a[n], b[n]; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; while(l+r<n){ if(l<n && r<n) m = (a[l]<b[r] ? a[l++]: b[r++]); else if(l<n) m = a[l++]; else m = b[r++]; } cout<<m<<endl; return 0; }
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)); int n = Integer.parseInt(br.readLine().trim()); String[] strArr = br.readLine().split(" "); int[] arr1 = new int[n]; for(int i = 0; i < n; i++) arr1[i] = Integer.parseInt(strArr[i]); strArr = br.readLine().split(" "); int[] arr2 = new int[n]; for(int i = 0; i < n; i++) arr2[i] = Integer.parseInt(strArr[i]); System.out.println(getUpMedian(arr1, 0, n - 1, arr2, 0, n - 1)); } // 两个数组的考虑范围大小(等长)必须相同 private static int getUpMedian(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2) { if(l1 == r1) return Math.min(arr1[l1], arr2[l2]); int mid1 = l1 + ((r1 - l1) >> 1); int mid2 = l2 + ((r2 - l2) >> 1); if(arr1[mid1] == arr2[mid2]) return arr1[mid1]; if((r1 - l1 + 1) % 2 == 0){ // 长度为偶数 if(arr1[mid1] < arr2[mid2]){ return getUpMedian(arr1, mid1 + 1, r1, arr2, l2, mid2); }else{ return getUpMedian(arr1, l1, mid1, arr2, mid2 + 1, r2); } }else{ // 长度为奇数 if(arr1[mid1] < arr2[mid2]){ return getUpMedian(arr1, mid1, r1, arr2, l2, mid2); }else{ return getUpMedian(arr1, l1, mid1, arr2, mid2, r2); } } } }
import java.util.Scanner; /** * @author zhuqiu * @date 2020/4/8 */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int len = in.nextInt(); int[] nums1 = new int[len]; int[] nums2 = new int[len]; for (int i = 0; i < len; i++) { nums1[i] = in.nextInt(); } for (int i = 0; i < len; i++) { nums2[i] = in.nextInt(); } Main instance = new Main(); int result = instance.findMedianSortedArrays(nums1, nums2); System.out.println(result); } public int findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int left = (m + n + 1) / 2; int right = (m + n + 2) / 2; return findKth(nums1, 0, nums2, 0, left); } public int findKth(int[] nums1, int i, int[] nums2, int j, int k) { if (i >= nums1.length) return nums2[j+k-1]; if (j >= nums2.length) return nums1[i+k-1]; if (k == 1) { return Math.min(nums1[i], nums2[j]); } int midValue1 = (i + k/2 -1 < nums1.length) ? nums1[i + k/2 -1] : Integer.MAX_VALUE; int midValue2 = (j + k/2 -1 < nums2.length) ? nums2[j + k/2 -1] : Integer.MAX_VALUE; if (midValue1 < midValue2) { return findKth(nums1, i + k/2, nums2, j, k - k/2); } else { return findKth(nums1, i, nums2, j + k/2, k - k/2); } } }
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; vector<int>arr1(n),arr2(n),arr(n); for(int i=0;i<n;i++) cin>>arr1[i]; for(int i=0;i<n;i++) cin>>arr2[i]; int j=0,j1=0,j2=0; while(j<n&&j1<n&&j2<n) { if(arr1[j1]<=arr2[j2]) { arr[j]=arr1[j1]; j++; j1++; } else if(arr1[j1]>arr2[j2]) { arr[j]=arr2[j2]; j++; j2++; } } cout<<arr[n-1]<<endl; return 0; }
import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int num=2*n; int[] arr=new int[num]; for(int i=0;i<num;i++){ arr[i]=sc.nextInt(); } Arrays.sort(arr); int sum=n/2; if(0==sum){ System.out.print(arr[sum]); }else{ System.out.print(arr[n-1]); } } }
#include<cstdio> // 取前半部分,排除后半部分 void prepart (int &low, int &high) { int mid = (low + high) / 2; high = mid; } // 取后半部分,排除前半部分 void postpart (int &low, int &high) { int mid = (low + high) / 2; if ((high-low+1) % 2 == 0) low = mid + 1; else low = mid; } int solve (int *a, int low1, int high1, int *b, int low2, int high2) { if (low1 == high1 && low2 == high2) return (a[low1] < b[low2] ? a[low1] : b[low2]); else { int mid1 = (low1 + high1) / 2; int mid2 = (low2 + high2) / 2; if (a[mid1] == b[mid2]) return a[mid1]; else if (a[mid1] > b[mid2]) { prepart(low1, high1); postpart(low2, high2); return solve(a, low1, high1, b, low2, high2); } else { prepart(low2, high2); postpart(low1, high1); return solve(a, low1, high1, b, low2, high2); } } } int main () { int i, n; scanf("%d", &n); int a[n], b[n]; for (i = 0; i < n; ++i) scanf("%d", &a[i]); for (i = 0; i < n; ++i) scanf("%d", &b[i]); printf("%d", solve(a, 0, n-1, b, 0, n-1)); return 0; }算法分析:由算法逻辑得出递推式:
#include<iostream> #include<limits.h> #include<vector> using namespace std; class Solution{ public: int find(vector<int> nums1,vector<int> nums2,int k){ if(k < 1 || k > nums1.size() + nums2.size()) return -1; int n = nums1.size(); int m = nums2.size(); int low = max(0,k-m); int high = min(n,k); //确定i的范围 while(low < high){ int mid = low + (high - low)/2; if(nums2[k-mid-1] > nums1[mid]){//这里的m=i,j=k-m,所以i+j=k,k-m-1相当于j-1即j前一个位置。j-1比i位置的值大,a数组i的位置往右移 low = mid + 1; }else{ high = mid; } } //判断low 是否为 0 或者为k 否者 第k个数为 max(num1[low-1] + num1[k-low -1])); int num1leftmax = low==0?INT_MIN:nums1[low-1]; int num2leftmax = low==k?INT_MIN:nums2[k-low-1]; return max(num1leftmax,num2leftmax); } }; int main(){ int N,K; cin>>N; vector<int> arr1(N); for(int i=0;i<N;i++){ cin>>arr1[i]; } vector<int> arr2(N); for(int i=0;i<N;i++){ cin>>arr2[i]; } Solution c1; cout<<c1.find(arr1,arr2,N)<<endl; return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int len=sc.nextInt(); int[] nums1=new int[len]; int[] nums2=new int[len]; for(int i=0;i<len;i++){ nums1[i]=sc.nextInt(); } for(int i=0;i<len;i++){ nums2[i]=sc.nextInt(); } int a=help(nums1,nums2); System.out.print(a); } public static int help(int[] nums1,int[] nums2){ int m=nums1.length; int n=nums2.length; if(m>n){ return help(nums2,nums1); } int iMin=0; int iMax=m; while(iMin<=iMax){ int i=(iMin+iMax)/2; int j=(m+n+1)/2-i; if(j!=0&&i!=m&&nums2[j-1]>nums1[i]){ iMin=i+1; }else if(i!=0&&j!=n&&nums1[i-1]>nums2[j]){ iMax=i-1; }else{ int maxLeft=0; if(i==0){ maxLeft=nums2[j-1]; }else if(j==0){ maxLeft=nums1[i-1]; }else{ maxLeft=Math.max(nums1[i-1],nums2[j-1]); } if((m+n)%2==1){ return maxLeft; } int minRight=0; if(i==m){ minRight=nums2[j]; }else if(j==n){ minRight=nums1[i]; }else{ minRight=Math.min(nums1[i],nums2[j]); } return Math.min(maxLeft,minRight); } } 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]){ e1 = mid1; s2 = mid2 + offset; } else if(a[mid1] < b[mid2]){ s1 = mid1 + offset; e2 = mid2; } else{ return a[mid1]; } } return min(a[s1], b[s2]); } int main(){ int n; scanf("%d", &n); vector<int> a(n), b(n); for(int i=0; i<2*n; i++){ if(i<n) scanf("%d", &a[i]); else scanf("%d", &b[i-n]); } int ans = getUpmid(a, 0, n-1, b, 0, n-1); cout << ans; return 0; }