分治法

原理
题目

原理

将问题拆分为几个子问题，而且这些子问题和原问题相似只是量级上小一些
递归地解决每一个子问题，然后结合这些子问题的解决方案构造出原问题的解决方案

分治法 = 分 + 治

归并排序
快速排序

题目

1. 快速指数

计算分治法 - 图1 。
https://leetcode-cn.com/problems/powx-n/

def fast_power(x, n):
    if n == 0:
        return 1
       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)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n == 1:
            return x
        ans = self.myPow(x, n >> 1)
        ans *= ans
        if n & 1 == 1:
            # 奇数
            ans *= x
        # print(ans)
        return ans

2. 搜索峰值

数组没有重复值，但可能存在多个峰值，返回任意一个峰值的index.
假设num[-1] = num[n] = -∞

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

顺序遍历一遍：nums[i - 1] < num[i] < num[i + 1], 最大时间复杂度O(n)

优化，O(logn)。二分法

3. 查找中值/查找第k个元素⭐⭐⭐⭐⭐

排序，选择第k个，时间复杂度O(nlogn)
O(n)的解法。参考快速排序

4. 两数组交集

给2个大小不一的数组，找出这两个数组的交集
输出中不能有重复

set.intersection(set1, set2 … etc) intersection() 方法用于返回两个或更多集合中都包含的元素，即交集。
两层循环，O(n^2)
查找时不用in，用二分查找。（m + n) logn
两个数组都排序，然后维护两个指针i，j。双指针

5. 两数组交集 II

给2个大小不一的数组，找出这两个数组的交集
输出中能有重复
Given nums1=[1, 2, 2, 1]，nums2=[2, 2]，return [2, 2]

排序，双指针

https://www.bilibili.com/video/BV1N4411Q7D1?p=17
6. 计算逆序对
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

暴力破解：两个循环，找出所有的序列对。O(n^2)
进一步优化，考虑O(nlgn)。
分治法

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[i]:
            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
def countInv(array):
    if len(array) < 2:
        return array, 0
    middle = len(array) // 2
    left, inv_left = countInv(array[:middle])
    right, inv_right = countInv(array[middle:])
    merged, count = merge(left, right)
    count += (inv_left + inv_right)
    return merged, count

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

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

暴力，O(n^2)
遍历当前元素 + 在另外一个数组使用二分查找。 O(nlgn)
双指针。 O(n)
思考，如何O(lgn)? 二分查找。

8. 在一个一维数组中找到连续的子序列，且这个子序列的加和值最大。

https://leetcode-cn.com/problems/maximum-subarray/

暴力，O(n^2)
暴力，对加法进行优化。O(n^2)，边找边加

DP。思考当前元素可能出现在连续子序列中吗？O(n)

class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
      localMax, globalMax = nums[0], nums[0]
      for num in nums[1:]:
          if localMax <= 0:
              localMax = num
          else:
              localMax += num
          globalMax = max(globalMax, localMax)
          # print(globalMax)
      return globalMax