给定两个有序数组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
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; 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]); } } }