162. Find Peak Element
https://leetcode.com/problems/find-peak-element/description/
這道題同樣使用Binary Search來(lái)解。當(dāng)選定一個(gè)mid時(shí)买置，會(huì)出現(xiàn)以下3種情況：
(1) num[m] > num[m - 1] && num[m] > num[m + 1]，說(shuō)明我們已經(jīng)找到波峰沛鸵，直接返回m即可跌前。
(2) num[m] < num[m - 1] && num[m] < num[m + 1]结序，說(shuō)明mid所在位置為波谷违寞，由于題目定義num[-1] = num[n] = -∞，所以兩邊都必定存在波峰契邀，怎么移動(dòng)都可以摆寄。
(3) num[m] > num[m - 1] && num[m] < num[m + 1] 或者 num[m] < num[m - 1] && num[m] > num[m + 1] 即mid處于上升或者下降階段，這時(shí)我們只要向大的方向前進(jìn)就一定可以找到波峰坯门。
代碼如下：
class Solution:
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1 or len(nums) >= 2 and nums[0] > nums[1]:
return 0
if len(nums) >= 2 and nums[-1] > nums[-2]:
return len(nums) - 1
left = 1
right = len(nums) - 2
while left <= right:
mid = (left + right) // 2
if nums[mid - 1] < nums[mid] > nums[mid + 1]:
return mid
if nums[mid - 1] > nums[mid] < nums[mid + 1]:
left = mid + 1
elif nums[mid - 1] < nums[mid] < nums[mid + 1]:
left = mid + 1
elif nums[mid - 1] > nums[mid] > nums[mid + 1]:
right = mid - 1
4. Median of Two Sorted Arrays
https://leetcode.com/problems/median-of-two-sorted-arrays/description/
這道題比較直接的想法就是用Merge Sorted Array這個(gè)題的方法把兩個(gè)有序數(shù)組合并微饥，當(dāng)合并到第(m+n)/2個(gè)元素的時(shí)候返回那個(gè)數(shù)即可，而且不用把結(jié)果數(shù)組存起來(lái)古戴。算法時(shí)間復(fù)雜度是O(m+n)欠橘，空間復(fù)雜度是O(1)。
接下來(lái)我們考慮有沒有優(yōu)化的算法现恼。優(yōu)化的思想來(lái)源于order statistics. 問題等價(jià)于求兩個(gè)array的第k=(m+n)/2（假設(shè)m和n分別是兩個(gè)數(shù)組的元素個(gè)數(shù)）大的數(shù)是多少肃续。基本思路是每次通過(guò)查看兩個(gè)數(shù)組的第k/2大的數(shù)(假設(shè)是A[k/2],B[k/2])叉袍，如果兩個(gè)A[k/2]=B[k/2]始锚，說(shuō)明當(dāng)前這個(gè)數(shù)即為兩個(gè)數(shù)組剩余元素的第k大的數(shù)，如果A[k/2]>B[k/2], 那么說(shuō)明B的前k/2個(gè)元素都不是我們要的第k大的數(shù)畦韭，反之則排除A的前k/2個(gè)疼蛾，如此每次可以排除k/2個(gè)元素肛跌，最終k=1時(shí)即為結(jié)果艺配。總的時(shí)間復(fù)雜度為O(logk),空間復(fù)雜度也是O(logk)衍慎，即為遞歸棧大小转唉。在這個(gè)題目中因?yàn)閗=(m+n)/2,所以復(fù)雜度是O(log(m+n))。
實(shí)現(xiàn)中還是有些細(xì)節(jié)要注意的稳捆，比如有時(shí)候剩下的數(shù)不足k/2個(gè)赠法，那么就得剩下的，而另一個(gè)數(shù)組則需要多取一些數(shù)乔夯。但是由于這種情況發(fā)生的時(shí)候砖织，不是把一個(gè)數(shù)組全部讀完，就是可以切除k/2個(gè)數(shù)末荐，所以不會(huì)影響算法的復(fù)雜度侧纯。
這道題的優(yōu)化算法主要是由order statistics派生而來(lái)，原型應(yīng)該是求topK的算法甲脏，這個(gè)問題是非常經(jīng)典的問題眶熬，一般有兩種解法妹笆，一種是用quick select(快速排序的subroutine),另一種是用heap。復(fù)雜度是差不多的娜氏，topK問題在海量數(shù)據(jù)處理中也是一個(gè)非常經(jīng)典的問題拳缠，所以還是要重視。
這道題還有一個(gè)O(log(min(m, n)))的解法贸弥，思路如下：
Given a sorted array A of length m, we can split it into two parts:
{ A[0], A[1], ... , A[i - 1] } | { A[i], A[i + 1], ... , A[m - 1] }
All elements in right part are greater than elements in left part.
The left part has "i" elements, and right part has "m - i" elements.
There are "m + 1" kinds of splits. (i = 0 ~ m)
When i = 0, the left part has "0" elements, right part has "m" elements.
When i = m, the left part has "m" elements, right part has "0" elements.
For array B, we can split it with the same way:
{ B[0], B[1], ... , B[j - 1] } | { B[j], B[j + 1], ... , B[n - 1] }
The left part has "j" elements, and right part has "n - j" elements.
Put A's left part and B's left part into one set. (Let's name this set "LeftPart")
Put A's right part and B's right part into one set. (Let's name this set "RightPart")
LeftPart??????????????????????????| RightPart
{ A[0], A[1], ... , A[i - 1] } | { A[i], A[i + 1], ... , A[m - 1] }
{ B[0], B[1], ... , B[j - 1] } | { B[j], B[j + 1], ... , B[n - 1] }
If we can ensure:
- LeftPart's length == RightPart's length (or RightPart's length + 1)
- All elements in RightPart are greater than elements in LeftPart.
then we split all elements in {A, B} into two parts with equal length, and one part is
always greater than the other part. Then the median can be easily found.
To ensure these two conditions, we just need to ensure:
(1) i + j == m - i + n - j (or: m - i + n - j + 1)
if n >= m, we just need to set:
i = 0 ~ m, j = (m + n + 1) / 2 - i
(2) B[j - 1] <= A[i] and A[i - 1] <= B[j]
considering edge values, we need to ensure:
(j == 0 or i == m or B[j - 1] <= A[i]) and
(i == 0 or j == n or A[i - 1] <= B[j])
So, all we need to do is:
Search i from 0 to m, to find an object "i" to meet condition (1) and (2) above
And we can do this search by binary search. How?
If B[j0 - 1] > A[i0], than the object "ix" can't be in [0, i0]. Why?
Because if ix < i0, than jx = (m + n + 1) / 2 - ix > j0,
than B[jx - 1] >= B[j0 - 1] > A[i0] >= A[ix].
This violates the condition (2). So ix can't be less than i0.
And if A[i0 - 1] > B[j0], than the object "ix" can't be in [i0, m].
So we can do the binary search following steps described below:
- set imin, imax = 0, m, than start searching in [imin, imax]
- i = (imin + imax) / 2; j = ((m + n + 1) / 2) - i
- if B[j - 1] > A[i]: continue searching in [i + 1, imax]
elif A[i - 1] > B[j]: continue searching in [imax, i]
else: bingo! this is our object "i"
When the object i is found, the median is:
max(A[i - 1], B[j - 1]) (when m + n is odd)
or (max(A[i - 1], B[j - 1]) + min(A[i], B[j])) / 2 (when m + n is even)
代碼如下：
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m, n = len(nums1), len(nums2)
if m > n:
return self.findMedianSortedArrays(nums2, nums1)
iMin = 0
iMax = m
while iMin <= iMax:
i = (iMin + iMax) // 2
j = (m + n + 1) // 2 - i
if i > 0 and j < n and nums1[i-1] > nums2[j]:
iMax = i - 1
elif i < m and j > 0 and nums2[j-1] > nums1[i]:
iMin = i + 1
else:
if i == 0:
num1 = nums2[j-1]
elif j == 0:
num1 = nums1[i-1]
else:
num1 = max(nums1[i-1], nums2[j-1])
if (m + n) % 2 == 1:
return num1
if i == m:
num2 = nums2[j]
elif j == n:
num2 = nums1[i]
else:
num2 = min(nums1[i], nums2[j])
return (num1 + num2) / 2
