[Python] 算法心得—数组篇

1 寻找最大的k个数

输入包含n个整数的数组，输出其中最大的k个数。
要求：输出的数字不能重复，如果k大于可输出数字的个数，便输出该数组从大到小的不重复排列。

如：
输入数组 nums=[2,1,3,3,4,4,5] 和 k=3，则输出[5,4,3];
输入数组 nums=[2,1,3,3,4,4,5] 和 k=100，则输出 [5,4,3,2,1]。

解法一：暴力排列法

直接将整个数组排序，取最后k位，显然写起来简单，但是总的时间复杂高。比如使用快速排序，然后再遍历序列中前k个元素，总的复杂度达到 O(n * log n) + O(k) = O(n * log n)。

实现代码：

def max_k(nums, k):
    nums = sorted(list(set(nums)))[::-1]
    return nums[-k:]

解法二：排列k个数

仔细想想，我们并没有必要对整个数组排序。假设k给定为3，也就是说要返回最大的三个数，我们可以采取以下代码实现：

def max_three(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    max1 = -sys.maxsize - 1
    max2 = -sys.maxsize - 1
    max3 = -sys.maxsize - 1
    nums = list(set(nums))
    for i in range(len(nums)):
        if nums[i] > max1:
            max3 = max2
            max2 = max1
            max1 = nums[i]

        elif nums[i] > max2:
            max3 = max2
            max2 = nums[i]

        elif nums[i] > max3:
            max3 = nums[i]
    if max3 != (-sys.maxsize - 1):
        return max3
    else:
        return max1

即定义三个变量（初始值为最小整数），然后遍历数组中的元素，保证这三个变量是当前遍历的最大的三个元素。此时的时间复杂度为O(n)。

那么如果k是变量呢？我们可以采用同样的思路，定义一个长度为k+1的数组（每个元素初始值均为最小整数），遍历数组，将元素插入数组中合适的位置，时间复杂度为 n * O(k) = O(nk) 具体实现代码如下。

import sys


def max_k(nums, k):
    arr_k = [-sys.maxsize - 1] * (k + 1)
    nums_set = list(set(nums))
    for i in range(len(nums_set)):
        if nums_set[i] > arr_k[k]:
            for j in range(k):
                if arr_k[j] < nums_set[i]:
                    arr_k.insert(j, nums_set[i])
                    break
    return arr_k[:min(k, len(nums_set))]

解法三：排列k个数（更优化）

参考一下快速排序的思想，在一个数组中选择一个基准点，然后将所有小于该基准点的数放置在基准点左边，所有大于该基准点的数放置在基准点右边，随后左右两个子数组继续寻找新的基准点不断递归，知道每个子数组均只包含一个数字。
那么我们可以将基准点设在k位置处，并且只递归k右边的子数组，时间复杂度为 O(k * log k) 具体代码实现如下：

def max_k(nums, k):
    my_list = list(set(nums))

    return solution(my_list, k)


def solution(my_list, k, start=None, end=None, pivot_k=False):
    start = 0 if start is None else start
    end = len(my_list) - 1 if end is None else end

    pivot_k = False if (k>len(my_list) and pivot_k) else pivot_k

    if start < end:
        i, j = start, end
        point = k if pivot_k else i
        while i != j:
            while my_list[j] >= my_list[point] and i < j:
                j = j - 1
            while my_list[i] <= my_list[point] and i < j:
                i = i + 1
            my_list[i], my_list[j] = my_list[j], my_list[i]
            if i == j:
                my_list[i], my_list[point] = my_list[point], my_list[i]
            if not pivot_k:
                solution(my_list, k, start, i - 1, pivot_k=False)
            solution(my_list, k, i + 1, end, pivot_k=False)

    return my_list[::-1][:k]

2.1 寻找和为定值的两个数

输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

解法一：暴力查找法

直接穷举，从数组中任意选两个数字，判断它们的和是否为给定数字，时间复杂度为O(N^2)。
或者我们也可以使用逆向思维，用给定数字target减去数组中的元素，判断结果是否存在于数组中，虽然时间复杂度仍为O(n^2)，但是代码实现比较方便：

def two_sum(nums, target):
    for x in nums:
        if (target - x) in nums:
           return [x, target - x]

解法二：构造哈希映射

通过构造哈希映射的方法，可以给定一个数字，根据哈希映射查找另一个数字是否也在数组中，只需用O(1)的时间，前提是经过O(N)时间的预处理，以及用O(N)的空间构造哈希表。

def two_sum(nums, target):
    nums = list(set(nums))
    mapper = {}
    for i in range(len(nums)):
        if nums[i] in mapper.values():
            return [nums[i], target - nums[i]]
        mapper[nums[i]] = target - nums[i]

解法三：二分查找

首先将数组进行排序，花费 O(N * log N)复杂度；随后遍历数组，对目标数减去每个元素进行二分查找，花费 N * O(log N) = O(N * log N)，具体代码如下：

def two_sum(nums, target):
    nums = sorted(nums)
    for i in range(len(nums)):
        l, r = i + 1, len(nums) - 1
        tmp = target - nums[i]
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == tmp:
                return [nums[i + 1], nums[mid + 1]]
            elif nums[mid] < tmp:
                l = mid + 1
            else:
                r = mid - 1

解法四：双指针查找

首先将数组排序，随后定义两个指针，分别指向数组首位两端，随后进行迭代：

如果nums[i] + nums[j] > target，则需要让两者和减少，所以i不变，j--；
如果nums[i] + nums[j] < target，则需要让两者和增大，所以j不变，i--；
如果nums[i] + nums[j] == target，跳出循环，返回nums[i]和nums[j]。

该算法的时间复杂度为 `O(N * log N + N) = O(N * log N)，实现代码如下：

def two_sum(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        if nums[l] + nums[r] == target:
            return [l + 1, r + 1]
        elif nums[l] + nums[r] < target:
            l += 1
        else:
            r -= 1

2.2 扩展：三数和

Leetcode 15题：给出一个数组，要求判断该数组中是否有三个数的和为0，并返回全部符合要求并且不重复的三个数，这里用了三个指针。

def three_sum(nums):
    result = []
    if len(nums) < 3:
        return result
    nums.sort()
    i = 0
    while i < len(nums) - 2:
        l, r = i + 1, len(nums) - 1
        b = nums[i]
        while l < r:
            a, c = nums[l], nums[r]
            if nums[l] + nums[i] + nums[r] == 0:
                result.append([nums[i], nums[l], nums[r]])
                while l < r and a == nums[l]:
                    l += 1
                while l < r and c == nums[r]:
                    r -= 1
            elif nums[l] + nums[i] + nums[r] < 0:
                l += 1
            else:
                r -= 1

        while i < len(nums) and b == nums[i]:
            i += 1

    return result

2.3 扩展：判断二叉树中有和为定值的根叶路径

Leetcode 112题：给定一个二叉树与一个给定值，判断二叉树中是否有根到叶和为该给定值的路径。

def has_path_sum(root, sum):
    if not root:
        return False

    if not root.left and not root.right and root.val == sum:
        return True

    sum -= root.val

    return has_path_sum(root.left, sum) or has_path_sum(root.right, sum)

3.1 最大连续子数组和

输入一个元素全为整数（有正有负）的数组，数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组和的最大值。

解法一：暴力求解法

三个for循环三层遍历，求出数组中每一个子数组的和，最终求出这些子数组的最大的一个值，时间复杂度为O(n^3)。

def max_subarray_c(arr):
    max_sum = a[0]
    cur_sum = 0
    n = len(arr)
    for i in range(n):
        for j in range(i, n):
            for k in range(i, j+1):
                cur_sum += arr[k]
            if cur_sum > max_sum:
                max_sum = cur_sum
            cur_sum = 0
    return max_sum

解法二：分治策略

首先找出数组中点mid = (low + high) // 2，随后将数组分为左右两部分。

寻找到的最大子数组arr[i,j+1]有三种情况：

完全位于数组左部分，即数组arr[low...mid]中，low<=i<=j<=mid；
完全位于数组右部分，即数组arr[mid...high]中，mid<i<=j<=high；
跨越了中点，即low<=i<=mid<j<=high

我们可以递归求解arr[low...mid]和arr[mid+1...high]的最大子数组，剩下的工作就是寻找跨越重点的最大子数组，并比较这三种情况中的最大者，时间复杂度为O(n * log n)。

def max_cross_subarray(arr, mid, low, high):
    now_left = arr[mid]
    left = arr[mid]
    for i in range(mid - 1, low - 1, -1):
        now_left = now_left + arr[i]
        if now_left > left:
            left = now_left
    now_right = arr[mid + 1]
    right = arr[mid + 1]
    for j in range(mid + 2, high + 1):
        now_right = now_right + arr[j]
        if now_right > right:
            right = now_right
    return left + right


def max_subarray(arr, low, high):
    if high == low:
        return arr[low]
    else:
        mid = (low + high) // 2
        m1 = max_subarray(arr, low, mid)
        m2 = max_subarray(arr, mid + 1, high)

        m3 = max_cross_subarray(arr, mid, low, high)

        result = max(m1, m2, m3)
        return result

解法三：迭代更新

假设cur_sum为当前最大子数组的和，max_sum为最后要返回的最大子数组的和，当我们进行迭代时：

对第j+1个元素有两种选择，要么放入前面找到的子数组，要么作为新子数组的第一个元素：
如果cur_sum加上当前元素arr[i]后不小于arr[i]，则令cur_sum加上arr[i]，否则cur_sum重新赋值为arr[i]。
同时，当cur_sum > max_sum，则更新max_sum = cur_sum，否则保持原值，不更新。

def max_subarray(arr):
    if not arr:
        return 0

    cur_sum = max_sum = arr[0]
    for num in arr[1:]:
        cur_sum = max(num, cur_sum + num)
        max_sum = max(max_sum, cur_sum)

    return max_sum

4.1 最大连续乘积子串

给一个浮点数序列，取最大乘积连续子串的值，例如：[-2.5, 4, 0, 3, 0.5, 8, -1]，则取出的最大乘积连续子串为[3, 0.5, 8]。

解法一：暴力遍历法

简单粗暴，两个for循环，时间复杂度O(N^2)：

def max_product_substring(a):
    max_res = a[0]
    for i in range(len(a)):
        x = 1
        for j in range(i, len(a)):
            x *= a[j]
            if x > max_res:
                max_res = x
    return max_res

解法二：迭代更新

这里仿照2.3.1中的解法，但需要注意的是，乘积子序列有正有负，我们可以同时找乘积最大与乘积最小的值（因为最小的负值有可能与另一个负值做乘积时成了最大的正值）。

def max_product_substring(a):
    max_end = a[0]
    min_end = a[0]
    max_res = a[0]
    for i in range(1, len(a)):
        end1 = max_end * a[i]
        end2 = min_end * a[i]
        max_end = max(max(end1, end2), a[i])
        min_end = min(min(end1, end2), a[i])
        max_res = max(max_res, max_end)
    return max_res