分治法

描述：

1、分：将问题柴分为几个子问题，这些子问题和原问题相似只是量级上小一些。

2、治：递归地解决每一个子问题，然后结合这些子问题的解决方案构造出原问题的解决方案。

例：二分搜索、快速排序、归并排序

习题

一、快速指数

题：计算 aⁿ

def fast_power(x, n):
    if n == 0:
        return 1.0
    elif n < 0:
        return 1 / fast_power(x, -n)
    elif n % 2:
        return fast_power(x * x, n // 2) * x
    else:
        return fast_power(x * x, n // 2)

二、搜索峰值

题：给定一个没有重复数的数组，其有多个峰值，返回任意一个峰值的index，You may imagine that num[-1] = num[n] = -∞.

def search_peak(alist):
    return peak_helper(alist, 0, len(alist) - 1)

def peak_helper(alist, start, end):
    if start == end:
        return start
    
    if (start + 1 == end):
        if alist[start] > alist[end]:
            return start
        return end
    
    mid = (start + end) // 2
    if alist[mid] > alist[mid - 1] and alist[mid] > alist[mid + 1]:
        return mid
    if alist[mid - 1] > alist[mid] and alist[mid] > alist[mid + 1]:
        return peak_helper(alist, start, mid - 1)
    return peak_helper(alist, mid + 1, end)

三、查找中值/第k个元素

方法一：排序：O(nlogn)

方法二：冒泡：O(nk)

方法三：快排：O(n)

# O(n) time, quick selection
def findKthLargest(nums, k):
    # convert the kth largest to smallest
    start = time.time()
    rst = findKthSmallest(nums, len(nums)+1-k)
    t = time.time() - start
    return rst, len(nums), t
    
def findKthSmallest(nums, k):
    if nums:
        pos = partition(nums, 0, len(nums)-1)
        if k > pos+1:
            return findKthSmallest(nums[pos+1:], k-pos-1)
        elif k < pos+1:
            return findKthSmallest(nums[:pos], k)
        else:
            return nums[pos]
 
# choose the right-most element as pivot   
def partition(nums, l, r):
    low = l
    while l < r:
        if nums[l] < nums[r]:
            nums[l], nums[low] = nums[low], nums[l]
            low += 1
        l += 1
    nums[low], nums[r] = nums[r], nums[low]
    return low

四、计算逆序对

题：对数组做逆序对计数—距离数组的排序结果还有“多远”。如果一个数组已经排 好序（升序），那么逆序对个数为0；如果数组是降序排列的，则逆序对个数最多。 在形式上，如果有两个元素a[i], a[j],如果a[i] > a[j] 且 i < j，那么a[i], a[j]构成一个逆序对。 例如序列2, 4, 1, 3, 5 有三个逆序对，分别是(2, 1), (4, 1), (4, 3)

方法一：O(n^2)

# O(n^2)
def countInv(arr):
    n = len(arr)
    inv_count = 0
    for i in range(n):
        for j in range(i+1, n):
            if (arr[i] > arr[j]):
                inv_count += 1
 
    return inv_count

方法二：归并O(nlogn)

def merge(left,right):
    result = list()
    i,j = 0,0
    inv_count = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        elif right[j] < left[i]:
            result.append(right[j])
            j += 1
            inv_count += (len(left)-i)
    result += left[i:]
    result += right[j:]
    return result,inv_count

# O(nlgn)
def countInvFast(array):
    if len(array) < 2:
        return array, 0
    middle = len(array) // 2
    left,inv_left = countInvFast(array[:middle])
    right,inv_right = countInvFast(array[middle:])
    merged, count = merge(left,right)
    count += (inv_left + inv_right)
    return merged, count

五、在已排序数组中找到多余元素的索引

题：给定两个排好序的数组。这两个数组只有一个不同的地方：在第一个数组某个位 置上多一个元素。请找到这个元素的索引位置

方法一：O(N)

## Returns index of extra element in arr1[].
def find_extra(arr1, arr2):
    for i in range(len(arr2)):
        if (arr1[i] != arr2[i]):
            return i
 
    return len(arr1)-1

方法二：O(logn)

def find_extra_fast(arr1, arr2):
    index = len(arr2)
    # left and right are end points denoting
    # the current range.
    left, right = 0, len(arr2) - 1
    while (left <= right):
        mid = (left + right) // 2;
 
        # If middle element is same of both
        # arrays, it means that extra element
        # is after mid so we update left to mid+1
        if (arr2[mid] == arr1[mid]):
            left = mid + 1
 
        # If middle element is different of the
        # arrays, it means that the index we are
        # searching for is either mid, or before
        # mid. Hence we update right to mid-1.
        else:
            index = mid
            right = mid - 1;
 
    # when right is greater than left our
    # search is complete.
    return index

六、加和值最大的子序列问题

方法一：O(n^2)

# O(n^2)
def subarray1(alist):
    result = -sys.maxsize
    for i in range(0, len(alist)):
        sum = 0
        for j in range (i, len(alist)):
            sum += alist[j]
            if sum > result:
                result = sum
    return result

方法二：分治

# O(n lgn)
def subarray2(alist):
    return subarray2_helper(alist, 0, len(alist)-1)

def subarray2_helper(alist, left, right):
    if (left == right):
        return alist[left]
    mid = (left + right) // 2
    return max(subarray2_helper(alist, left, mid), 
               subarray2_helper(alist, mid+1, right), 
               maxcrossing(alist, left, mid, right))

def maxcrossing(alist, left, mid, right):
    sum = 0
    left_sum = -sys.maxsize
    for i in range (mid, left-1, -1):
        sum += alist[i]
        if (sum > left_sum):
            left_sum = sum
            
    sum = 0
    right_sum = -sys.maxsize
    for i in range (mid+1, right+1):
        sum += alist[i]
        if (sum > right_sum):
            right_sum = sum        

    return left_sum + right_sum

方法三：动态规划

# O(n)
def subarray3(alist):
    result = -sys.maxsize
    local = 0
    for i in alist:
        local = max(local + i, i)
        result = max(result, local)
    return result