LeetCode #162 #81 2018-08-16

162. Find Peak Element

https://leetcode.com/problems/find-peak-element/description/

这道题同样使用Binary Search来解。当选定一个mid时，会出现以下3种情况：
(1) num[m] > num[m - 1] && num[m] > num[m + 1]，说明我们已经找到波峰，直接返回m即可。
(2) num[m] < num[m - 1] && num[m] < num[m + 1]，说明mid所在位置为波谷，由于题目定义num[-1] = num[n] = -∞，所以两边都必定存在波峰，怎么移动都可以。
(3) num[m] > num[m - 1] && num[m] < num[m + 1] 或者 num[m] < num[m - 1] && num[m] > num[m + 1] 即mid处于上升或者下降阶段，这时我们只要向大的方向前进就一定可以找到波峰。
代码如下：

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这个题的方法把两个有序数组合并，当合并到第(m+n)/2个元素的时候返回那个数即可，而且不用把结果数组存起来。算法时间复杂度是O(m+n)，空间复杂度是O(1)。

接下来我们考虑有没有优化的算法。优化的思想来源于order statistics. 问题等价于求两个array的第k=(m+n)/2（假设m和n分别是两个数组的元素个数）大的数是多少。基本思路是每次通过查看两个数组的第k/2大的数(假设是A[k/2],B[k/2])，如果两个A[k/2]=B[k/2]，说明当前这个数即为两个数组剩余元素的第k大的数，如果A[k/2]>B[k/2], 那么说明B的前k/2个元素都不是我们要的第k大的数，反之则排除A的前k/2个，如此每次可以排除k/2个元素，最终k=1时即为结果。总的时间复杂度为O(logk),空间复杂度也是O(logk)，即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。
实现中还是有些细节要注意的，比如有时候剩下的数不足k/2个，那么就得剩下的，而另一个数组则需要多取一些数。但是由于这种情况发生的时候，不是把一个数组全部读完，就是可以切除k/2个数，所以不会影响算法的复杂度。
这道题的优化算法主要是由order statistics派生而来，原型应该是求topK的算法，这个问题是非常经典的问题，一般有两种解法，一种是用quick select(快速排序的subroutine),另一种是用heap。复杂度是差不多的，topK问题在海量数据处理中也是一个非常经典的问题，所以还是要重视。

这道题还有一个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:

1. LeftPart's length == RightPart's length (or RightPart's length + 1)
2. 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:

1. set imin, imax = 0, m, than start searching in [imin, imax]
2. i = (imin + imax) / 2; j = ((m + n + 1) / 2) - i
3. 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