พื้นฐานอาร์เรย์และการดำเนินการในที่เดิม

อาร์เรย์ในฐานะหน่วยความจำต่อเนื่อง

nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2])       # 30
print(nums[-1])      # 50

# O(1) append (amortised)
nums.append(60)
print(nums)          # [10,20,30,40,50,60]

# O(n) insert at beginning
nums.insert(0, 0)    # shifts all elements right
print(nums)          # [0,10,20,30,40,50,60]

นับเกินหรือนับขาด: ข้อผิดพลาดคลาสสิกของอาร์เรย์

def find_max(nums):
    # Use len(nums)-1 as last index
    max_val = nums[0]              # safe if n >= 1
    for i in range(1, len(nums)):  # start at 1, not 0
        if nums[i] > max_val:
            max_val = nums[i]
    return max_val

print(find_max([3, 1, 4, 1, 5]))  # 5
print(find_max([7]))               # 7  (single element)
# Would crash if we accessed nums[len(nums)]

การกลับลำดับในข้อมูลเดิมด้วยตัวชี้สองตัว

def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left  += 1
        right -= 1
    # Space: O(1)  Time: O(n)

a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a)  # [5, 4, 3, 2, 1]

b = [1, 2, 3]
reverse_inplace(b)
print(b)  # [3, 2, 1]  middle element unchanged

การหมุนอาร์เรย์ในข้อมูลเดิม

def rotate(nums, k):
    n = len(nums)
    k %= n  # handle k >= n

    def rev(l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1; r -= 1

    rev(0, n-1)    # reverse all
    rev(0, k-1)    # reverse first k
    rev(k, n-1)    # reverse rest

a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a)  # [5, 6, 7, 1, 2, 3, 4]

การลบสมาชิกในข้อมูลเดิม

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write  # new length

nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len])  # [2, 2]

nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2])  # [0, 1, 3, 0, 4]

ย้ายเลขศูนย์: ตัวชี้อ่าน-เขียน

def move_zeroes(nums):
    write = 0
    # Move all non-zeroes to front
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    # Fill rest with zeroes
    while write < len(nums):
        nums[write] = 0
        write += 1

a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a)  # [1, 3, 12, 0, 0]

ยกกำลังสองและเรียงลำดับในอาร์เรย์เดิม

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1  # fill from the right
    while left <= right:
        l_sq = nums[left]  ** 2
        r_sq = nums[right] ** 2
        if l_sq > r_sq:
            result[pos] = l_sq
            left += 1
        else:
            result[pos] = r_sq
            right -= 1
        pos -= 1
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]

การหาจุดหมุนและการแบ่งส่วน

def sort_colors(nums):
    # Dutch national flag: 0s, 1s, 2s
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1  # don't advance mid: new nums[mid] unexamined

a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a)  # [0, 0, 1, 1, 2, 2]

การแก้ไขสมาชิกอาร์เรย์ขณะวนซ้ำ

def find_disappeared(nums):
    # Mark visited by negating the value at the index
    for n in nums:
        idx = abs(n) - 1
        if nums[idx] > 0:
            nums[idx] *= -1  # mark as seen
    # Indices with positive values are missing
    return [i + 1 for i, v in enumerate(nums) if v > 0]

print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6]  -- O(n) time, O(1) extra space

รายการตรวจสอบรูปแบบโจทย์อาร์เรย์สำหรับการสัมภาษณ์

def max_profit(prices):
    # Pattern: single scan, track running minimum
    # Time: O(n), Space: O(1)
    if not prices: return 0  # edge case: empty
    min_price = prices[0]
    max_prof  = 0
    for price in prices[1:]:  # start at index 1
        max_prof  = max(max_prof, price - min_price)
        min_price = min(min_price, price)
    return max_prof

print(max_profit([7, 1, 5, 3, 6, 4]))  # 5
print(max_profit([7, 6, 4, 3, 1]))     # 0

อัลกอริทึมของ Kadane: ผลรวมช่วงย่อยสูงสุด

def max_subarray(nums):
    current = global_max = nums[0]
    for n in nums[1:]:
        current    = max(n, current + n)  # extend or restart
        global_max = max(global_max, current)
    return global_max

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6  (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1  (all negative: take the least negative)

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทบทวนบทเรียน