注：学习左老师的算法题最优解的记录。
题目：
给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
举例：
arr1=[1,2,3,4]，arr2=[3,4,5,6]
总共有8个数，那么上中位数是第4小的数，所以返回3。
arr1=[0,1,2]，arr2=[3,4,5]
总共有6个数，那么上中位数是第3小的数，所以返回2。
要求：
时间复杂度为O(logN)，额外空间复杂度为O(1)。
/** * Created by Engin on 2017-03-09. * 题目：P465 * 在两个长度相等的排序数组中找到上中位数 */ public class P465 { private static int [] arr1 = {0, 1, 102, 103, 104}; private static int [] arr2 = {3, 4, 99, 100, 101}; public static void main(String[] args) { System.out.println(get(arr1, arr2)); } public static int get(int [] arr1, int [] arr2){ if(arr1 == null || arr2 == null || arr1.length != arr2.length){ return -1; } int start1 = 0; int end1 = arr1.length - 1; int start2 = 0; int end2 = arr2.length - 1; int mid1 = 0;// 位置 int mid2 = 0; int offset = 0;// 为0是奇数，为1是偶数 while (start1 < end1){ mid1 = (start1 + end1) / 2; mid2 = (start2 + end2) / 2; // if(arr1.length % 2 == 0){// 判断奇偶性 // offset = 1; // }else{ // offset = 0; // } offset = ((end1 - start1 + 1) & 1) ^ 1;// 优化之后的判断奇偶性的方法 if(arr1[mid1] > arr2[mid2]){ end1 = mid1; start2 = mid2 + offset; }else if(arr1[mid1] < arr2[mid2]){ start1 = mid1 + offset; end2 = mid2; }else{ return arr1[mid1]; } } return Math.min(arr1[start1], arr2[start2]); } }
