算法（3）：數(shù)組

??一鼓作氣，再而衰，三而竭，第三篇走起！

數(shù)組（Array）

??數(shù)組是大家再熟悉不過的東西了，但是這里還是簡單說一下，數(shù)組是連續(xù)存放一系列元素的數(shù)據(jù)結(jié)構(gòu)，我們可以方便的通過索引訪問數(shù)組當(dāng)中的任何一個元素。通常，數(shù)組在定義時是固定大小的，但是也有一種動態(tài)數(shù)組，它在初始化時不需要定義數(shù)組大小，也就意味著可以無限裝數(shù)據(jù)，我們稱之為動態(tài)數(shù)組，如C++當(dāng)中的Vector（曾經(jīng)是我最喜歡的一個數(shù)據(jù)結(jié)構(gòu)，當(dāng)然，在我遇到python當(dāng)中的List之前）和Java當(dāng)中的ArrayList 。

安利一波問題4，大家一定要看一看。

問題1：找到一個一維數(shù)組的“中樞”元素的索引。如果有很多中樞元素，則只需返回最左側(cè)的即可。中樞在此處意味著該索引左側(cè)元素和等于該索引右側(cè)元素和。
輸入: [1, 2, 8, 4, 5, 6]
輸出: 3（1+2+8 = 5+6）

代碼，那是異常的簡單啊。小編不禁想起了有一次面試，面試官讓我寫一個找數(shù)組中最大最小值的算法，啊，那時的時光是多么美好！如下代碼的時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

def pivotIndex(nums) -> int:
    ts, cs = sum(nums), 0
    for idx, num in enumerate(nums):
        ls, rs = cs, ts - cs - num
        if ls == rs:
            return idx
        cs += num
    return -1

if __name__ == '__main__':
    ans = pivotIndex([1, 2, 8, 4, 5, 6])
    print(ans)

問題2：加1操作。將輸入數(shù)組當(dāng)成一個整數(shù)，然后執(zhí)行加1操作
例子：
輸入: [1,2,3] 輸出: [1,2,4]
輸入: [9,9,9] 輸出: [1,0,0,0]

我的方法是直接在數(shù)組里面執(zhí)行操作，當(dāng)然你也可以換種方法，如把數(shù)組里元素按位讀出來變成int，然后加一，然后在按位存放到數(shù)組中。

def plusOne(digits: list) -> list:
    digits = [0] + digits
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] == 9:
            digits[i] = 0
        else:
            digits[i] += 1
            break

    return (digits, digits[1:])[0 if digits[0] != 0 else 1]

if __name__ == '__main__':
    ans = plusOne([1, 2, 8, 4, 5, 6])
    print(ans)

問題3：對角線遍歷二維數(shù)組(Diagonal Traverse)。
一維數(shù)組一般都很簡單，但是到了二維數(shù)組，難度就會上升一個臺階，畢竟，問題的花樣變多了嘛~
輸入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
輸出: [1,2,4,7,5,3,6,8,9]
如果看不懂的話，可以配上下面這張圖看，保證一眼就明白~

對角線遍歷矩陣圖

代碼具體思路分為兩步：
step1：根據(jù)對角線將矩陣分組（可以發(fā)現(xiàn)，同一對角線的矩陣row和col坐標(biāo)相加為定值），如上圖，可以分為5組，得到[1] , [2,4]，[3,5,7]，[6,8]，[9]。
step2：按照（row + col）的大小順序?qū)?shù)據(jù)依次添加到結(jié)果列表當(dāng)中。根據(jù)代碼定義，在（row + col ）為偶數(shù)時，需要翻轉(zhuǎn)一下該組元素。即[3,5,7]（此時row + col = 2）需要變?yōu)閇7,5,3]再添加到結(jié)果中。

import  collections
def findDiagonalOrder(matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[int]
    """
    result = []
    dd = collections.defaultdict(list)
    if not matrix: return result
    # Step 1: Numbers are grouped by the diagonals.
    # Numbers in same diagonal have same value of row+col
    for i in range(0, len(matrix)):
        for j in range(0, len(matrix[0])):
            dd[i + j].append(matrix[i][j])  # starting indices from 1, hence i+j+1.
    # Step 2: Place diagonals in the result list.
    # But remember to reverse numbers in odd diagonals.
    for k in sorted(dd.keys()):
        if k % 2 == 0: dd[k].reverse()
        result += dd[k]
    return result

if __name__ == '__main__':
    arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
    ans = findDiagonalOrder(arr)
    print(ans)

問題4：旋轉(zhuǎn)矩陣（Spiral Matrix），即返回一個矩陣順時針旋轉(zhuǎn)的結(jié)果。
輸入：
[ [ 1, 2, 3 ],
?[ 4, 5, 6 ],
?[ 7, 8, 9 ] ]
輸出：[1,2,3,6,9,8,7,4,5]

下面這個答案是我在網(wǎng)上找的，看到這個代碼之后的好久時間里，我的嘴巴只能發(fā)出“wo cao”這兩個音。。?？吹竭@段代碼，我仿佛戀愛了。

def spiralOrder(matrix: list) -> list:
    return matrix and [*matrix.pop(0)] + spiralOrder([*zip(*matrix)][::-1])

if __name__ == '__main__':
    arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
    ans = spiralOrder(arr)
    print(ans)

問題5：數(shù)組求和。給定一個升序排列的數(shù)組，找出兩個數(shù)，其和等于輸入‘target’，結(jié)果返回這兩個數(shù)的索引。
輸入: numbers = [2,7,11,15], target = 9
輸出: [1,2]
我們?nèi)绻褂帽┝Ψǖ脑挘Y(jié)果有C^2_n種，時間復(fù)雜度為O(n^2)。那么大家還記不記得 有一招從天而降的掌法... 上一章講解的雙指針技術(shù)呢？這里便用到了！兩個指針分別從左和右開始向中間走，兩個數(shù)的和大了，右指針左移，和偏小，左指針右移......

# 四個問題不吉利，小編拍胸脯保證，馬上（百年之內(nèi)）把第五個問題補起來！
def twoSum(numbers: list, target: int) -> list:
    i, j = 0, len(numbers) - 1
    while i < j:
        if numbers[i] + numbers[j] == target:
            return [i, j]
        elif numbers[i] + numbers[j] > target:
            j -= 1
        else:
            i += 1
    return []

if __name__ == '__main__':
    numbers = [2, 7, 11, 15]
    target = 9
    ans = twoSum(numbers,target)
    print(ans)

問題6：移除特定值（寫五道已經(jīng)達(dá)到我的標(biāo)準(zhǔn)了，奈何又看到一個較為經(jīng)典的案例，那就......再來個雙指針教學(xué)吧~），將數(shù)組當(dāng)中等于’target'的值移除掉，空間復(fù)雜度限定為O(1)，最后結(jié)果返回新數(shù)組長度。
例子：
輸入：[1,2,7,4,4,5],target = 4
輸出：4 （新數(shù)組為[1,2,7,5]，所以長度為4）
快指針遍歷數(shù)組，慢指針則作為新數(shù)組的尾部。只有當(dāng)快指針?biāo)傅闹岛汀畉arget’不同時，才會執(zhí)行賦值以及p+=1操作，相同時直接跳過該數(shù)。

def removeElement(numbers: list, target: int) -> int:
    p = 0
    for i in range(len(numbers)):
        if numbers[i] != target:
            numbers[p] = numbers[i]
            p +=1
    return p

if __name__ == '__main__':
    numbers = [1,7,3,4,4,5]
    target = 4
    ans = removeElement(numbers,target)
    print(ans)
    print(numbers[:ans])

問題7:滿足要求的最小子數(shù)組(Minimum Size Subarray Sum)。不好意思我忍不住又添了一道......該題給定n只包含正整數(shù)的數(shù)組，以及一個整數(shù)s，要求是找到一個最小長度的連續(xù)子數(shù)組，該子數(shù)組的元素和≥s。 如果不存在，則返回0。
輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2（子數(shù)組 [4,3] 是滿足題目約束的最小數(shù)組）
運行下面程序會輸出每步變量信息，大家可以自己讀讀試試，看能否理解~如果不理解可以留言探討，現(xiàn)在已經(jīng)晚上11點了，小編扛不住，這道題就不寫分析了......

def minSubArrayLen( s: int, nums: list) -> int:
    total = left = 0
    result = len(nums) + 1
    for right, num in enumerate(nums):
        total += num
        while total >= s:
            result = min(result, right - left + 1)
            total -= nums[left]
            left += 1
            print('total:',total,'result:',result,'left:',left,'right:',right)
    return result if result <= len(nums) else 0

if __name__ == '__main__':
    numbers = [2,3,1,2,4,3]
    target = 7
    ans = minSubArrayLen(target,numbers)
    print(ans)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容