[Python] 算法心得—數(shù)組篇

1 尋找最大的k個數(shù)

輸入包含n個整數(shù)的數(shù)組丘喻，輸出其中最大的k個數(shù)。
要求：輸出的數(shù)字不能重復，如果k大于可輸出數(shù)字的個數(shù)撮执，便輸出該數(shù)組從大到小的不重復排列。

如：
輸入數(shù)組 nums=[2,1,3,3,4,4,5] 和 k=3汽馋，則輸出[5,4,3];
輸入數(shù)組 nums=[2,1,3,3,4,4,5] 和 k=100纺讲，則輸出 [5,4,3,2,1]未檩。

解法一：暴力排列法

直接將整個數(shù)組排序蕾总，取最后k位粥航，顯然寫起來簡單，但是總的時間復雜高生百。比如使用快速排序递雀，然后再遍歷序列中前k個元素，總的復雜度達到 O(n * log n) + O(k) = O(n * log n)蚀浆。

實現(xiàn)代碼：

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

解法二：排列k個數(shù)

仔細想想缀程，我們并沒有必要對整個數(shù)組排序搜吧。假設k給定為3，也就是說要返回最大的三個數(shù)杨凑，我們可以采取以下代碼實現(xiàn)：

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

即定義三個變量（初始值為最小整數(shù)）滤奈，然后遍歷數(shù)組中的元素，保證這三個變量是當前遍歷的最大的三個元素撩满。此時的時間復雜度為O(n)蜒程。

那么如果k是變量呢？我們可以采用同樣的思路鹦牛，定義一個長度為k+1的數(shù)組（每個元素初始值均為最小整數(shù)）搞糕，遍歷數(shù)組勇吊，將元素插入數(shù)組中合適的位置曼追，時間復雜度為 n * O(k) = O(nk) 具體實現(xiàn)代碼如下。

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個數(shù)（更優(yōu)化）

參考一下快速排序的思想汉规，在一個數(shù)組中選擇一個基準點礼殊，然后將所有小于該基準點的數(shù)放置在基準點左邊，所有大于該基準點的數(shù)放置在基準點右邊针史，隨后左右兩個子數(shù)組繼續(xù)尋找新的基準點不斷遞歸晶伦，知道每個子數(shù)組均只包含一個數(shù)字。
那么我們可以將基準點設在k位置處啄枕，并且只遞歸k右邊的子數(shù)組婚陪，時間復雜度為 O(k * log k) 具體代碼實現(xiàn)如下：

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 尋找和為定值的兩個數(shù)

輸入一個數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)频祝，使得它們的和正好是輸入的那個數(shù)字泌参。
例如輸入數(shù)組1、2常空、4沽一、7、11漓糙、15和數(shù)字15铣缠。由于4+11=15，因此輸出4和11昆禽。

解法一：暴力查找法

直接窮舉蝗蛙，從數(shù)組中任意選兩個數(shù)字，判斷它們的和是否為給定數(shù)字醉鳖，時間復雜度為O(N^2)捡硅。
或者我們也可以使用逆向思維，用給定數(shù)字target減去數(shù)組中的元素辐棒，判斷結果是否存在于數(shù)組中病曾，雖然時間復雜度仍為O(n^2)牍蜂，但是代碼實現(xiàn)比較方便：

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

解法二：構造哈希映射

通過構造哈希映射的方法，可以給定一個數(shù)字泰涂，根據(jù)哈希映射查找另一個數(shù)字是否也在數(shù)組中鲫竞，只需用O(1)的時間，前提是經(jīng)過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]

解法三：二分查找

首先將數(shù)組進行排序，花費 O(N * log N)復雜度是牢；隨后遍歷數(shù)組僵井，對目標數(shù)減去每個元素進行二分查找，花費 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

解法四：雙指針查找

首先將數(shù)組排序批什，隨后定義兩個指針，分別指向數(shù)組首位兩端社搅，隨后進行迭代：

如果nums[i] + nums[j] > target驻债，則需要讓兩者和減少，所以i不變形葬，j--合呐；
如果nums[i] + nums[j] < target，則需要讓兩者和增大笙以，所以j不變淌实，i--；
如果nums[i] + nums[j] == target猖腕，跳出循環(huán)拆祈，返回nums[i]和nums[j]。

該算法的時間復雜度為 `O(N * log N + N) = O(N * log N)谈息，實現(xià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 擴展：三數(shù)和

Leetcode 15題：給出一個數(shù)組缘屹，要求判斷該數(shù)組中是否有三個數(shù)的和為0，并返回全部符合要求并且不重復的三個數(shù)侠仇，這里用了三個指針轻姿。

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 最大連續(xù)子數(shù)組和

輸入一個元素全為整數(shù)（有正有負）的數(shù)組互亮，數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和余素，求所有子數(shù)組和的最大值豹休。

解法一：暴力求解法

三個for循環(huán)三層遍歷，求出數(shù)組中每一個子數(shù)組的和桨吊，最終求出這些子數(shù)組的最大的一個值威根，時間復雜度為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

解法二：分治策略

首先找出數(shù)組中點mid = (low + high) // 2，隨后將數(shù)組分為左右兩部分洛搀。

尋找到的最大子數(shù)組arr[i,j+1]有三種情況：

完全位于數(shù)組左部分敢茁，即數(shù)組arr[low...mid]中，low<=i<=j<=mid留美；
完全位于數(shù)組右部分彰檬，即數(shù)組arr[mid...high]中，mid<i<=j<=high谎砾；
跨越了中點逢倍，即low<=i<=mid<j<=high

我們可以遞歸求解arr[low...mid]和arr[mid+1...high]的最大子數(shù)組，剩下的工作就是尋找跨越重點的最大子數(shù)組景图，并比較這三種情況中的最大者较雕，時間復雜度為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為當前最大子數(shù)組的和症歇，max_sum為最后要返回的最大子數(shù)組的和郎笆，當我們進行迭代時：

對第j+1個元素有兩種選擇谭梗，要么放入前面找到的子數(shù)組忘晤，要么作為新子數(shù)組的第一個元素：
如果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 最大連續(xù)乘積子串

給一個浮點數(shù)序列序六，取最大乘積連續(xù)子串的值，例如：[-2.5, 4, 0, 3, 0.5, 8, -1]蚤吹，則取出的最大乘積連續(xù)子串為[3, 0.5, 8]例诀。

解法一：暴力遍歷法

簡單粗暴，兩個for循環(huán)裁着，時間復雜度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