Leetcode 4 Median of Two Sorted Arrays

流川疯

发布于 2022-05-10 19:05:54

1880

发布于 2022-05-10 19:05:54

文章被收录于专栏：流川疯编写程序的艺术

4. Median of Two Sorted Arrays

Total Accepted: 99662 Total Submissions: 523759

Difficulty: Hard

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)).

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

方案0：合并两个数组为一个数组，排序，取第k个

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = nums1.size();
        int n = nums2.size();
        vector<int>   v;   
		v.insert(v.end(),   nums1.begin(),   nums1.end());   
		v.insert(v.end(),   nums2.begin(),   nums2.end()); 
		
        
        
        sort(v.begin(),v.end());
        
        double median=(double) ((n+m)%2? v[(n+m)/2]:(v[(n+m-1)/2]+v[(n+m)/2])/2.0);
        
        
        
        return median;
    }
};

方案1：假设两个数组总共有n个元素，用merge sort的思路排序，排序好的数组取出下标为k-1的元素就是我们需要的答案。这个方法比较容易想到，但是有没有更好的方法呢？

方案2：可以用一个计数器，记录当前已经找到第m大的元素。同时我们使用两个指针pA和pB，分别指向A和B数组的第一个元素。使用类似于merge sort的原理，如果数组A当前元素小，那么pA++，同时m++。如果数组B当前元素小，那么pB++，同时m++。最终当m等于k的时候，就得到了我们的答案——O(k)时间，O(1)空间。

但是，当k很接近于n的时候，这个方法还是很费时间的。当然，我们可以判断一下，如果k比n/2大的话，我们可以从最大的元素开始找。但是如果我们要找所有元素的中位数呢？时间还是O(n/2)=O(n)的。有没有更好的方案呢？

我们可以考虑从k入手。如果我们每次都能够剔除一个一定在第k大元素之前的元素，那么我们需要进行k次。但是如果每次我们都剔除一半呢？所以用这种类似于二分的思想，我们可以这样考虑： Assume that the number of elements in A and B are both larger than k/2, and if we compare the k/2-th smallest element in A(i.e. A[k/2-1]) and the k-th smallest element in B(i.e. B[k/2 - 1]), there are three results: (Becasue k can be odd or even number, so we assume k is even number here for simplicy. The following is also true when k is an odd number.) A[k/2-1] = B[k/2-1] A[k/2-1] > B[k/2-1] A[k/2-1] < B[k/2-1] if A[k/2-1] < B[k/2-1], that means all the elements from A[0] to A[k/2-1](i.e. the k/2 smallest elements in A) are in the range of k smallest elements in the union of A and B. Or, in the other word, A[k/2 - 1] can never be larger than the k-th smalleset element in the union of A and B. Why? We can use a proof by contradiction. Since A[k/2 - 1] is larger than the k-th smallest element in the union of A and B, then we assume it is the (k+1)-th smallest one. Since it is smaller than B[k/2 - 1], then B[k/2 - 1] should be at least the (k+2)-th smallest one. So there are at most (k/2-1) elements smaller than A[k/2-1] in A, and at most (k/2 - 1) elements smaller than A[k/2-1] in B.So the total number is k/2+k/2-2, which, no matter when k is odd or even, is surly smaller than k(since A[k/2-1] is the (k+1)-th smallest element). So A[k/2-1] can never larger than the k-th smallest element in the union of A and B if A[k/2-1]<B[k/2-1]; Since there is such an important conclusion, we can safely drop the first k/2 element in A, which are definitaly smaller than k-th element in the union of A and B. This is also true for the A[k/2-1] > B[k/2-1] condition, which we should drop the elements in B. When A[k/2-1] = B[k/2-1], then we have found the k-th smallest element, that is the equal element, we can call it m. There are each (k/2-1) numbers smaller than m in A and B, so m must be the k-th smallest number. So we can call a function recursively, when A[k/2-1] < B[k/2-1], we drop the elements in A, else we drop the elements in B. We should also consider the edge case, that is, when should we stop? 1. When A or B is empty, we return B[k-1]( or A[k-1]), respectively; 2. When k is 1(when A and B are both not empty), we return the smaller one of A[0] and B[0] 3. When A[k/2-1] = B[k/2-1], we should return one of them In the code, we check if m is larger than n to garentee that the we always know the smaller array, for coding simplicy.

中文翻译：

该方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题，原问题也得以解决。

首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。如果A[k/2-1]<B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。

证明也很简单，可以采用反证法。假设A[k/2-1]大于合并之后的第k小值，我们不妨假定其为第（k+1）小值。由于A[k/2-1]小于B[k/2-1]，所以B[k/2-1]至少是第（k+2）小值。但实际上，在A中至多存在k/2-1个元素小于A[k/2-1]，B中也至多存在k/2-1个元素小于A[k/2-1]，所以小于A[k/2-1]的元素个数至多有k/2+ k/2-2，小于k，这与A[k/2-1]是第（k+1）的数矛盾。

当A[k/2-1]>B[k/2-1]时存在类似的结论。

当A[k/2-1]=B[k/2-1]时，我们已经找到了第k小的数，也即这个相等的元素，我们将其记为m。由于在A和B中分别有k/2-1个元素小于m，所以m即是第k小的数。(这里可能有人会有疑问，如果k为奇数，则m不是中位数。这里是进行了理想化考虑，在实际代码中略有不同，是先求k/2，然后利用k-k/2获得另一个数。)

通过上面的分析，我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件：

如果A或者B为空，则直接返回B[k-1]或者A[k-1]；
如果k为1，我们只需要返回A[0]和B[0]中的较小值；
如果A[k/2-1]=B[k/2-1]，返回其中一个；

// leetcode4.cpp : 定义控制台应用程序的入口点。
//


#include "stdafx.h"

#define min(x,y) (x>y?y:x)
#define max(x,y) (x>y?x:y)

double findKth(int a[],int m,int b[],int n,int k)
{
	if (m>n)
		return findKth(b,n,a,m,k);
	if(m == 0)
		return b[k-1];
	if(k ==1)
		return min(a[0],b[0]);

	//divide k into two parts;
	int pa = min(k/2,m),pb = k - pa;
	if (a[pa -1]<b[pb - 1])
		return findKth(a +pa,m-pa,b,n,k-pa);
	else if(a[pa -1]>a[pb-1])
		return findKth(a,m,b+pb,n-pb,k-pb);
	else
		return a[pa -1];

}

double findMedianSortedArrays(int A[],int m,int B[],int n)
{
	int total = m +n;
	if (total&0x1)
		return findKth(A,m,B,n,total/2+1);
	else
		return (findKth(A,m,B,n,total/2)+findKth(A,m,B,n,total/2+1))/2;
}
int _tmain(int argc, _TCHAR* argv[])
{
	int a[]={1,2,3};
	int b[]={555,666,999};
	int result = findMedianSortedArrays(a,3,b,3);
	return 0;
}

python解决方案：基本上和c++比较类似

def findMedianSortedArrays(self, A, B):
    l = len(A) + len(B)
    if l % 2 == 1:
        return self.kth(A, B, l // 2)
    else:
        return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2.defkth(self, a, b, k):ifnot a:
        return b[k]
    ifnot b:
        return a[k]
    ia, ib = len(a) // 2 , len(b) // 2
    ma, mb = a[ia], b[ib]

    # when k is bigger than the sum of a and b's median indices if ia + ib < k:
        # if a's median is bigger than b's, b's first half doesn't include kif ma > mb:
            return self.kth(a, b[ib + 1:], k - ib - 1)
        else:
            return self.kth(a[ia + 1:], b, k - ia - 1)
    # when k is smaller than the sum of a and b's indiceselse:
        # if a's median is bigger than b's, a's second half doesn't include kif ma > mb:
            return self.kth(a[:ia], b, k)
        else:
            return self.kth(a, b[:ib], k)

参考文献：

http://blog.csdn.net/zxzxy1988/article/details/8587244

http://blog.csdn.net/yutianzuijin/article/details/11499917

网上看到了一张leetcode 的难度和考试频率分析表，转过来给大家看看，出现频率为5的题目还是背诵并默写吧，哈哈！


1	Two Sum	2	5	array	sort
				set	Two Pointers
2	Add Two Numbers	3	4	linked list	Two Pointers
					Math
3	Longest Substring Without Repeating Characters	3	2	string	Two Pointers
				hashtable
4	Median of Two Sorted Arrays	5	3	array	Binary Search
5	Longest Palindromic Substring	4	2	string
6	ZigZag Conversion	3	1	string
7	Reverse Integer	2	3		Math
8	String to Integer (atoi)	2	5	string	Math
9	Palindrome Number	2	2		Math
10	Regular Expression Matching	5	3	string	Recursion
					DP
11	Container With Most Water	3	2	array	Two Pointers
12	Integer to Roman	3	4		Math
13	Roman to Integer	2	4		Math
14	Longest Common Prefix	2	1	string
15	3Sum	3	5	array	Two Pointers
16	3Sum Closest	3	1	array	Two Pointers
17	Letter Combinations of a Phone Number	3	3	string	DFS
18	4Sum	3	2	array
19	Remove Nth Node From End of List	2	3	linked list	Two Pointers
20	Valid Parentheses	2	5	string	Stack
21	Merge Two Sorted Lists	2	5	linked list	sort
					Two Pointers
					merge
22	Generate Parentheses	3	4	string	DFS
23	Merge k Sorted Lists	3	4	linked list	sort
				heap	Two Pointers
					merge
24	Swap Nodes in Pairs	2	4	linked list
25	Reverse Nodes in k-Group	4	2	linked list	Recursion
					Two Pointers
26	Remove Duplicates from Sorted Array	1	3	array	Two Pointers
27	Remove Element	1	4	array	Two Pointers
28	Implement strStr()	4	5	string	Two Pointers
					KMP
					rolling hash
29	Divide Two Integers	4	3		Binary Search
					Math
30	Substring with Concatenation of All Words	3	1	string	Two Pointers
31	Next Permutation	5	2	array	permutation
32	Longest Valid Parentheses	4	1	string	DP
33	Search in Rotated Sorted Array	4	3	array	Binary Search
34	Search for a Range	4	3	array	Binary Search
35	Search Insert Position	2	2	array
36	Valid Sudoku	2	2	array
37	Sudoku Solver	4	2	array	DFS
38	Count and Say	2	2	string	Two Pointers
39	Combination Sum	3	3	array	combination
40	Combination Sum II	4	2	array	combination
41	First Missing Positive	5	2	array	sort
42	Trapping Rain Water	4	2	array	Two Pointers
					Stack
43	Multiply Strings	4	3	string	Two Pointers
					Math
44	Wildcard Matching	5	3	string	Recursion
					DP
					greedy
45	Jump Game II	4	2	array
46	Permutations	3	4	array	permutation
47	Permutations II	4	2	array	permutation
48	Rotate Image	4	2	array
49	Anagrams	3	4	string
				hashtable
50	Pow(x, n)	3	5		Binary Search
					Math
51	N-Queens	4	3	array	DFS
52	N-Queens II	4	3	array	DFS
53	Maximum Subarray	3	3	array	DP
54	Spiral Matrix	4	2	array
55	Jump Game	3	2	array
56	Merge Intervals	4	5	array	sort
				linked list	merge
				red-black tree
57	Insert Interval	4	5	array	sort
				linked list	merge
				red-black tree
58	Length of Last Word	1	1	string
59	Spiral Matrix II	3	2	array
60	Permutation Sequence	5	1		permutation
					Math
61	Rotate List	3	2	linked list	Two Pointers
62	Unique Paths	2	3	array	DP
63	Unique Paths II	3	3	array	DP
64	Minimum Path Sum	3	3	array	DP
65	Valid Number	2	5	string	Math
66	Plus One	1	2	array	Math
67	Add Binary	2	4	string	Two Pointers
					Math
68	Text Justification	4	2	string
69	Sqrt(x)	4	4		Binary Search
70	Climbing Stairs	2	5		DP
71	Simplify Path	3	1	string	Stack
72	Edit Distance	4	3	string	DP
73	Set Matrix Zeroes	3	5	array
74	Search a 2D Matrix	3	3	array	Binary Search
75	Sort Colors	4	2	array	sort
					Two Pointers
76	Minimum Window Substring	4	2	string	Two Pointers
77	Combinations	3	4		combination
78	Subsets	3	4	array	Recursion
					combination
79	Word Search	3	4	array	DFS
80	Remove Duplicates from Sorted Array II	2	2	array	Two Pointers
81	Search in Rotated Sorted Array II	5	3	array	Binary Search
82	Remove Duplicates from Sorted List II	3	3	linked list	Recursion
					Two Pointers
83	Remove Duplicates from Sorted List	1	3	linked list
84	Largest Rectangle in Histogram	5	2	array	Stack
85	Maximal Rectangle	5	1	array	DP
					Stack
86	Partition List	3	3	linked list	Two Pointers
87	Scramble String	5	2	string	Recursion
					DP
88	Merge Sorted Array	2	5	array	Two Pointers
					merge
89	Gray Code	4	2		combination
90	Subsets II	4	2	array	Recursion
					combination
91	Decode Ways	3	4	string	Recursion
					DP
92	Reverse Linked List II	3	2	linked list	Two Pointers
93	Restore IP Addresses	3	3	string	DFS
94	Binary Tree Inorder Traversal	4	3	tree	Recursion
				hashtable	morris
					Stack
95	Unique Binary Search Trees II	4	1	tree	DP
					DFS
96	Unique Binary Search Trees	3	1	tree	DP
97	Interleaving String	5	2	string	Recursion
					DP
98	Validate Binary Search Tree	3	5	tree	DFS
99	Recover Binary Search Tree	4	2	tree	DFS
100	Same Tree	1	1	tree	DFS
101	Symmetric Tree	1	2	tree	DFS
102	Binary Tree Level Order Traversal	3	4	tree	BFS
103	Binary Tree Zigzag Level Order Traversal	4	3	queue	BFS
				tree	Stack
104	Maximum Depth of Binary Tree	1	1	tree	DFS
105	Construct Binary Tree from Preorder and Inorder Tr	3	3	array	DFS
				tree
106	Construct Binary Tree from Inorder and Postorder T	3	3	array	DFS
				tree
107	Binary Tree Level Order Traversal II	3	1	tree	BFS
108	Convert Sorted Array to Binary Search Tree	2	3	tree	DFS
109	Convert Sorted List to Binary Search Tree	4	3	linked list	Recursion
					Two Pointers
110	Balanced Binary Tree	1	2	tree	DFS
111	Minimum Depth of Binary Tree	1	1	tree	DFS
112	Path Sum	1	3	tree	DFS
113	Path Sum II	2	2	tree	DFS
114	Flatten Binary Tree to Linked List	3	3	tree	Recursion
					Stack
115	Distinct Subsequences	4	2	string	DP
116	Populating Next Right Pointers in Each Node	3	3	tree	DFS
117	Populating Next Right Pointers in Each Node II	4	2	tree	DFS
118	Pascal's Triangle	2	1	array
119	Pascal's Triangle II	2	1	array
120	Triangle	3	1	array	DP
121	Best Time to Buy and Sell Stock	2	1	array	DP
122	Best Time to Buy and Sell Stock II	3	1	array	greedy
123	Best Time to Buy and Sell Stock III	4	1	array	DP
124	Binary Tree Maximum Path Sum	4	2	tree	DFS
125	Valid Palindrome	2	5	string	Two Pointers
126	Word Ladder II	1	1
127	Word Ladder	3	5	graph	BFS
					shortest path
128	Longest Consecutive Sequence	4	3	array
129	Sum Root to Leaf Numbers	2	4	tree	DFS
130	Surrounded Regions	4	3	array	BFS
					DFS
131	Palindrome Partitioning	3	4	string	DFS
132	Palindrome Partitioning II	4	3	string	DP