-
Notifications
You must be signed in to change notification settings - Fork 1
/
key004.java
71 lines (70 loc) · 2.25 KB
/
key004.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}
//☆☆☆☆☆
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
//Trick:分别找第 (m+n+1) / 2 个和 第(m+n+2) / 2 个,然后求其平均值即可
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
//i: nums1的起始位置 j: nums2的起始位置
public int findKth(int[] nums1, int i, int[] nums2, int j, int k){
if( i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
if( j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
if(k == 1) return Math.min(nums1[i], nums2[j]);
int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
if(midVal1 < midVal2){
return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
}else{
return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
}
}
}