Leetcode 4 Median of Two Sorted Arrays

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個

方案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]>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]，傳回其中一個；

python解決方案：基本上和c++比較類似

參考文獻：

<a target="_blank" href="http://blog.csdn.net/zxzxy1988/article/details/8587244">http://blog.csdn.net/zxzxy1988/article/details/8587244</a>

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

網上看到了一張leetcode 的難度和考試頻率分析表，轉過來給大家看看，出現頻率為5的題目還是背誦并默寫吧，哈哈！

1

Two Sum

2

5

array

sort

set

Two Pointers

Add Two Numbers

3

4

linked list

Math

Longest Substring Without Repeating Characters

string

hashtable

Median of Two Sorted Arrays

Binary Search

Longest Palindromic Substring

6

ZigZag Conversion

7

Reverse Integer

8

String to Integer (atoi)

9

Palindrome Number

10

Regular Expression Matching

Recursion

DP

11

Container With Most Water

12

Integer to Roman

13

Roman to Integer

14

Longest Common Prefix

15

3Sum

16

3Sum Closest

17

Letter Combinations of a Phone Number

DFS

18

4Sum

19

Remove Nth Node From End of List

20

Valid Parentheses

Stack

21

Merge Two Sorted Lists

merge

22

Generate Parentheses

23

Merge k Sorted Lists

heap

24

Swap Nodes in Pairs

25

Reverse Nodes in k-Group

26

Remove Duplicates from Sorted Array

27

Remove Element

28

Implement strStr()

KMP

rolling hash

29

Divide Two Integers

30

Substring with Concatenation of All Words

31

Next Permutation

permutation

32

Longest Valid Parentheses

33

Search in Rotated Sorted Array

34

Search for a Range

35

Search Insert Position

36

Valid Sudoku

37

Sudoku Solver

38

Count and Say

39

Combination Sum

combination

40

Combination Sum II

41

First Missing Positive

42

Trapping Rain Water

43

Multiply Strings

44

Wildcard Matching

greedy

45

Jump Game II

46

Permutations

47

Permutations II

48

Rotate Image

49

Anagrams

50

Pow(x, n)

51

N-Queens

52

N-Queens II

53

Maximum Subarray

54

Spiral Matrix

55

Jump Game

56

Merge Intervals

red-black tree

57

Insert Interval

58

Length of Last Word

59

Spiral Matrix II

60

Permutation Sequence

61

Rotate List

62

Unique Paths

63

Unique Paths II

64

Minimum Path Sum

65

Valid Number

66

Plus One

67

Add Binary

68

Text Justification

69

Sqrt(x)

70

Climbing Stairs

71

Simplify Path

72

Edit Distance

73

Set Matrix Zeroes

74

Search a 2D Matrix

75

Sort Colors

76

Minimum Window Substring

77

Combinations

78

Subsets

79

Word Search

80

Remove Duplicates from Sorted Array II

81

Search in Rotated Sorted Array II

82

Remove Duplicates from Sorted List II

83

Remove Duplicates from Sorted List

84

Largest Rectangle in Histogram

85

Maximal Rectangle

86

Partition List

87

Scramble String

88

Merge Sorted Array

89

Gray Code

90

Subsets II

91

Decode Ways

92

Reverse Linked List II

93

Restore IP Addresses

94

Binary Tree Inorder Traversal

tree

morris

95

Unique Binary Search Trees II

96

Unique Binary Search Trees

97

Interleaving String

98

Validate Binary Search Tree

99

Recover Binary Search Tree

100

Same Tree

101

Symmetric Tree

102

Binary Tree Level Order Traversal

BFS

103

Binary Tree Zigzag Level Order Traversal

queue

104

Maximum Depth of Binary Tree

105

Construct Binary Tree from Preorder and Inorder Tr

106

Construct Binary Tree from Inorder and Postorder T

107

Binary Tree Level Order Traversal II

108

Convert Sorted Array to Binary Search Tree

109

Convert Sorted List to Binary Search Tree

110

Balanced Binary Tree

111

Minimum Depth of Binary Tree

112

Path Sum

113

Path Sum II

114

Flatten Binary Tree to Linked List

115

Distinct Subsequences

116

Populating Next Right Pointers in Each Node

117

Populating Next Right Pointers in Each Node II

118

Pascal's Triangle

119

Pascal's Triangle II

120

Triangle

121

Best Time to Buy and Sell Stock

122

Best Time to Buy and Sell Stock II

123

Best Time to Buy and Sell Stock III

124

Binary Tree Maximum Path Sum

125

Valid Palindrome

126

Word Ladder II

127

Word Ladder

graph

shortest path

128

Longest Consecutive Sequence

129

Sum Root to Leaf Numbers

130

Surrounded Regions

131

Palindrome Partitioning

132

Palindrome Partitioning II