leeyupeng

leeyupeng@126.com

0%

leetcode.4.寻找两个有序数组的中位数

发表于 更新于 分类于 ， 阅读次数： Valine：

寻找两个有序数组的中位数

问题描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

归并法

思路分析

将两个有序数组归并排序为一个数组C,求出数组C的中位数

代码实现

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
class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		int m = nums1.size();
		int n = nums2.size();
		vector<int> nums(m + n);
		int i = 0, j = 0;
		for (int k = 0; k < m+n; k++)
		{
			if (i == m)
			{
				nums[k] = nums2[j];
				j++;
			}
			else if (j == n)
			{
				nums[k] = nums1[i];
				i++;
			}
			else if(nums1[i] <= nums2[j])
			{
				nums[k] = nums1[i];
				i++;
			}
			else
			{
				nums[k] = nums2[j];
				j++;
			}
		}

		if ((m+n) % 2 == 1)
		{
			return nums[(m + n) / 2];
		}
		else
		{
			return (nums[(m + n) / 2 - 1] + nums[(m + n) / 2]) * 0.5f;
		}
	}
};

双指针

思路分析

  • i=0,j=0起始 0<=i<=m,0<=j<=n
  • A[i]<B[j] i++
  • A[i]>B[j] j++
  • i + j = (m+n+1)/2 停止

代码实现

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
class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		int i = 0, j = 0;
		int m = nums1.size();
		int n = nums2.size();
		while (i + j < (m + n + 1) / 2)
		{
			if (i == m)
			{
				j++;
			}
			else if (j == n)
			{
				i++;
			}
			else if(nums1[i] <= nums2[j])
			{
				i++;
			}
			else
			{
				j++;
			}
		}

		int max_left = 0;
		if (i == 0)
		{
			max_left = nums2[j - 1];
		}
		else if (j == 0)
		{
			max_left = nums1[i - 1];
		}
		else
		{
			max_left = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
		}

		if ((m+n) % 2 == 1)
		{

			return max_left;
		}

		int min_right = 0;
		if (i == m)
		{
			min_right = nums2[j];
		}
		else if (j == n)
		{
			min_right = nums1[i];
		}
		else
		{
			min_right = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
		}
		return (max_left+min_right) * 0.5f;
	}
};

二分法

思路分析

  • 1.假设中位数的位置在 A B 数组的 i,j位置 0<=i<=m,0<=j<=n
    则满足：
    • 1.i+j = (m+n+1)/2
    • 2.集合A(0,i-1)和集合B(0,j-1) 小于 集合A(i,m-1)和集合B(j,n-1)
  • 2.临界处理
    • 1.数组为空
    • 2.i==0 j==0 i==m j==n

代码实现

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
72
73
74
75
76
class Solution {
public:
	int Bisection(vector<int>& nums1, vector<int>& nums2, int i, int j)
	{
		int index1 = (i + j) / 2;
		int index2 = (nums1.size() + nums2.size() + 1) / 2 - index1;

		if (index1 < nums1.size() && index2 <= nums2.size() && nums1[index1] < nums2[index2 - 1])
		{
			return Bisection(nums1, nums2, index1 + 1, j);
		}
		else if (index1 > 0 && index2 <nums2.size() && nums1[index1 - 1] > nums2[index2])
		{
			return Bisection(nums1, nums2, i, index1 - 1);
		}
		return index1;
	}
	double findMedianSortedArrays2(vector<int>& nums1, vector<int>& nums2)
	{
		int i = 0, j = nums1.size();
		i = (nums1.size() - nums2.size() + 1) / 2;
		i = i >= 0 ? i : 0;
		j = (nums1.size() + nums2.size() + 1) / 2;
		j = j <= nums1.size() ? j : nums1.size();

		int index1 = Bisection(nums1,nums2,i,j);
		int index2 = (nums1.size() + nums2.size() + 1) / 2 - index1;

		int max_left;
		if (index1 == 0)
		{
			max_left = nums2[index2 - 1];
		}
		else if (index2 == 0)
		{
			max_left = nums1[index1 - 1];
		}
		else
		{
			max_left = nums1[index1 - 1] > nums2[index2 - 1] ? nums1[index1 - 1] : nums2[index2 - 1];
		}

		if ((nums1.size() + nums2.size()) % 2 == 1)
		{
			return max_left;
		}

		int min_right;
		if (index1 == nums1.size())
		{
			min_right = nums2[index2];
		}
		else if (index2 == nums2.size())
		{
			min_right = nums1[index1];
		}
		else
		{
			min_right = nums1[index1] < nums2[index2] ? nums1[index1] : nums2[index2];
		}
		return (max_left + min_right) * 0.5f;

	}

	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		if (nums1.size() > nums2.size())
		{
			return findMedianSortedArrays2(nums2,nums1);
		}
		else
		{
			return findMedianSortedArrays2(nums1, nums2);
		}
	}
};

代码实现优化

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{

		int m = nums1.size();
		int n = nums2.size();
		int i = 0;
		int j = (m + n + 1) / 2 - i;
		int iMin = 0, iMax = m;
		if (m == 0)
		{
			i = 0;
			j = (m + n + 1) / 2;
		}
		else if (n == 0)
		{
			i = (m + n + 1) / 2;
			j = 0;
		}
		else
		{
			while (iMin <= iMax)
			{
				i = (iMin + iMax) / 2;
				j = (m + n + 1) / 2 - i;

				if (j < 0)
				{
					iMax = i - 1;
					continue;
				}
				else if (j > n)
				{
					iMin = i + 1;
					continue;
				}

				if (i == m)
				{
					if (nums1[i - 1] <= nums2[j])
					{
						break;
					}
					else
					{
						iMax = i - 1;
						continue;
					}
				}
				else if (i == 0)
				{
					if (nums1[i] >= nums2[j - 1])
					{
						break;
					}
					else
					{
						iMin = i + 1;
						continue;
					}
				}

				if (j == n)
				{
					if (nums1[i] >= nums2[j - 1])
					{
						break;
					}
					else
					{
						iMin = i + 1;
						continue;
					}
				}
				else if (j == 0)
				{
					if (nums1[i - 1] <= nums2[j])
					{
						break;
					}
					else
					{
						iMax = i - 1;
						continue;
					}
				}
				if (nums1[i - 1] > nums2[j])
				{
					iMax = i - 1;
				}
				else if (nums1[i] < nums2[j - 1])
				{
					iMin = i + 1;
				}
				else
				{
					break;
				}
			}
		}

		int max_left = 0;
		if (i == 0)
		{
			max_left = nums2[j - 1];
		}
		else if (j == 0)
		{
			max_left = nums1[i - 1];
		}
		else
		{
			max_left = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
		}

		if ((m + n) % 2 == 1)
		{

			return max_left;
		}

		int min_right = 0;
		if (i == m)
		{
			min_right = nums2[j];
		}
		else if (j == n)
		{
			min_right = nums1[i];
		}
		else
		{
			min_right = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
		}
		return (max_left + min_right) * 0.5f;
	}
};

有序数组第K小的元素

思路分析

通过求有序数组第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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
class Solution {
public:
	int findKSortedArraysBisection(vector<int>& nums1, vector<int>& nums2, int k)
	{
		int m = nums1.size();
		int n = nums2.size();
		int i = 0;
		int j = k - i;
		int iMin = 0, iMax = m;
		if (m == 0)
		{
			i = 0;
			j = k;
		}
		else if (n == 0)
		{
			i = k;
			j = 0;
		}
		else
		{
			while (iMin <= iMax)
			{
				i = (iMin + iMax) / 2;
				j = k - i;

				if (j < 0)
				{
					iMax = i - 1;
					continue;
				}
				else if (j > n)
				{
					iMin = i + 1;
					continue;
				}

                if (i == m && j == n)
				{
					break;
				}

				if (i == m)
				{
					if (nums1[i - 1] <= nums2[j])
					{
						break;
					}
					else
					{
						iMax = i - 1;
						continue;
					}
				}
				else if (i == 0)
				{
					if (nums1[i] >= nums2[j - 1])
					{
						break;
					}
					else
					{
						iMin = i + 1;
						continue;
					}
				}

				if (j == n)
				{
					if (nums1[i] >= nums2[j - 1])
					{
						break;
					}
					else
					{
						iMin = i + 1;
						continue;
					}
				}
				else if (j == 0)
				{
					if (nums1[i - 1] <= nums2[j])
					{
						break;
					}
					else
					{
						iMax = i - 1;
						continue;
					}
				}
				if (nums1[i - 1] > nums2[j])
				{
					iMax = i - 1;
				}
				else if (nums1[i] < nums2[j - 1])
				{
					iMin = i + 1;
				}
				else
				{
					break;
				}
			}
		}

		int max_left = 0;
		if (i == 0)
		{
			max_left = nums2[j - 1];
		}
		else if (j == 0)
		{
			max_left = nums1[i - 1];
		}
		else
		{
			max_left = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
		}
		return max_left;
	}
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		int n = nums1.size();
		int m = nums2.size();
		if ((n + m) % 2 == 1)
		{
			return findKSortedArraysBisection(nums1,nums2,(n+m)/2 + 1);
		}
		else
		{
			return (findKSortedArraysBisection(nums1, nums2, (n + m) / 2) + findKSortedArraysBisection(nums1, nums2, (n + m) / 2 + 1)) * 0.5f;
		}
	}
};