LeetCode4. Median of Two Sorted Arrays

发表于 | 分类于 |

代码思路

  • 转化为查找第K个数
  • 二分查找
点击显/隐代码
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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int len1 = nums1.length;
		int len2 = nums2.length;

		// 分治~二分查找
		int low = 0;
		int high = len1;

		while (true) {
			// index1 代表 nums1 在左侧的个数，取值范围 [0，len1];
			int index1 = low + (high - low) / 2;
			int index2 = (len1 - index1 + len2) / 2;

			// 对应的左边下边
			int i = index1 - 1;
			int j = index2 - 1;

			// 边界情况
			if (index1 == 0) {
				if (nums2[index2 - 1] <= nums1[index1]) {
					if(index2 == len2) return (nums1[index1] + nums2[index2-1])/2.0;
					return (nums2[index2 - 1] + Math.min(nums1[index1], nums2[index2])) / 2.0;
				} else {
					low = index1 + 1;
				}
			} else if (index2 == len2) {
				if (nums2[index2 - 1] <= nums1[index1]) {
					if(index1 == 0) return (nums1[index1] + nums2[index2-1])/2.0;
					return (Math.max(nums1[index1 - 1], nums2[index2 - 1]) + nums1[index1]) / 2.0;
				} else {
					// index1 取小了
					low = index1 + 1;
				}
			} else if (index2 == 0) {
				if (nums1[index1 - 1] <= nums2[index2]) {
					if (index1 == len1)
						return (nums1[index1 - 1] + nums2[index2]) / 2.0;
					return (nums1[index1 - 1] + Math.min(nums1[index1], nums2[index2])) / 2.0;
				} else {
					high = index1;
				}
			} else if (index1 == len1) {
				if (nums1[index1 - 1] <= nums2[index2]) {
					if (index2 == 0)
						return (nums1[index1 - 1] + nums2[index2]) / 2.0;
					return (Math.max(nums1[index1 - 1], nums2[index2 - 1]) + nums2[index2]) / 2.0;
				} else {
					high = index1;
				}
			}

			else if (nums1[index1 - 1] <= nums2[index2] && nums2[index2 - 1] <= nums1[index1]) {
				return (Math.max(nums1[index1 - 1], nums2[index2 - 1]) + Math.min(nums1[index1], nums2[index2])) / 2.0;
			} else if (nums1[index1 - 1] > nums2[index2] || nums2[index2 - 1] > nums1[index1]) {
				high = index1;
			} else {
				low = index1;
			}
		}

	}