There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
时间复杂度为(m+n)log(m+n)，想不出比这更优的了。
基本思路是：
稍后补上，要吃饭了。。。
1 class Solution {
2 class Pair {
3 int mid1;
4 int mid2;
5
6 public Pair(int mid1, int mid2) {
7 this.mid1 = mid1;
8 this.mid2 = mid2;
9 }
10 }
11
12 public Pair binarySearch(int[] a, int target) {
13 int low = 0, high = a.length, mid = (low + high) / 2;
14 while (low <= high && low < a.length) {
15 mid = (low + high) / 2;
16 if (a[mid] == target) {
17 while (mid<a.length-1 && a[mid+1]==target) ++mid;
18 return new Pair(mid, mid);
19 } else if (target < a[mid]) {
20 high = mid - 1;
21 } else {
22 low = mid + 1;
23 }
24 }
25 Pair pair = null;
26 if (low == mid) {
27 if (mid > high) {
28 int t = mid;
29 mid = high;
30 high = t;
31 }
32 pair = new Pair(mid, high);
33 } else {
34 if (low > mid) {
35 int t = low;
36 low = mid;
37 mid = t;
38 }
39 pair = new Pair(low, mid);
40 }
41 return pair;
42 }
43
44 public double result(int[] nums1, int low1, int high1, int[] nums2, int low2, int high2) {
45 int totalLength = nums1.length + nums2.length;
46 int mid1, mid2;
47 int right = -1, left = -1;
48 boolean isOdd = (totalLength % 2 == 0) ? false : true;
49
50 while (low2 <= high2 && low2< nums2.length && high2<= nums2.length) {// && res <= totalLength / 2
51 mid2 = (low2 + high2) / 2;
52 Pair pair = binarySearch(nums1, nums2[mid2]);
53 int res = pair.mid1 + 1 + mid2 + 1;
54 if (res == totalLength / 2) {
55 if (!isOdd) { //总个数为偶数
56 if (pair.mid1 > 0) {
57 if (pair.mid1 + 1 >= nums1.length) {
58 if (mid2 == nums2.length - 1) {
59 System.out.println("目测这种情况不会发生1");
60 } else {
61 return (nums2[mid2]+nums2[mid2+1])/2.0;
62 }
63 } else {
64 if (mid2 == nums2.length - 1) {
65 return (nums2[mid2] + nums1[pair.mid1+1])/2.0;
66 } else {
67 left = nums2[mid2];
68 right = (nums1[pair.mid1 + 1] > nums2[mid2 + 1]) ? nums2[mid2 + 1] : nums1[pair.mid1 + 1];
69 }
70 }
71 return (left + right) / 2.0;
72 } else {
73 if (mid2 >= 0 && mid2 < nums2.length) {
74 left = nums2[mid2];
75 if (mid2+1>=nums2.length){
76 right= nums1[pair.mid1+1];
77 }else {
78 right= nums1[pair.mid1+1] > nums2[mid2+1]?nums2[mid2+1]:nums1[pair.mid1+1];
79 }
80 } else {
81 System.out.println("目测这种情况不会发生3");
82 }
83 return (left + right) / 2.0;
84 }
85 } else { // 总个数为奇数
86 if (pair.mid1+1< nums1.length){
87 if (nums2.length==1){
88 return nums1[pair.mid1+1];
89 }
90 if (mid2+1< nums2.length){
91 return nums1[pair.mid1+1] < nums2[mid2+1]?nums1[pair.mid1+1]:nums2[mid2+1];
92 }else {
93 return nums1[pair.mid1+1];
94 }
95 }else {
96 return nums2[mid2+1];
97 }
98 }
99 }
100 if (res == totalLength / 2 + 1) {
101 if (!isOdd) { // 总个数为偶数
102 if (pair.mid1 == -1){
103 return (nums2[mid2]+nums2[mid2-1])/2.0;
104 }else {
105 if (mid2-1>=0) {
106 left = (nums1[pair.mid1] > nums2[mid2 - 1]) ? nums1[pair.mid1] : nums2[mid2 - 1];
107 right = nums2[mid2];
108 return (left + right) / 2.0;
109 }else {
110 left = pair.mid1;
111 right = mid2;
112 return (nums1[left] + nums2[right]) / 2.0;
113 }
114 }
115 } else { // 总个数为奇数
116 return nums2[mid2];
117 }
118 }
119 if (res<totalLength/2+1){
120 low2=mid2+1;
121 }else {
122 high2=mid2-1;
123 }
124 }
125 return -1.0;
126 }
127
128 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
129 /**
130 * 当某个数组为空时单独判断
131 * */
132 int left=-1,right=-1;
133 if (nums1.length==0){
134 if (nums2.length==0){
135 System.out.println("目测这种情况不会发生5");
136 }else {
137 if (nums2.length%2==0){
138 left=nums2[nums2.length/2-1];
139 right=nums2[nums2.length/2];
140 return (left+right)/2.0;
141 }else {
142 return nums2[nums2.length/2];
143 }
144 }
145 }
146 if (nums2.length==0){
147 if (nums1.length==0){
148 System.out.println("目测这种情况不会发生6");
149 }else {
150 if (nums1.length%2==0){
151 left=nums1[nums1.length/2-1];
152 right=nums1[nums1.length/2];
153 return (left+right)/2.0;
154 }else {
155 return nums1[nums1.length/2];
156 }
157 }
158 }
159 if (nums1.length==1 && nums2.length==1){
160 return (nums1[0]+nums2[0])/2.0;
161 }
162 double res = result(nums1, 0, nums1.length, nums2, 0, nums2.length);
163 if (res == -1)
164 return result(nums2,0,nums2.length,nums1,0, nums1.length);
165 return res;
166 }
167 }