OMG运维

数组

TIP

数组使用一组连续的内存空间，来存储一组具有相同类型的数据。

数组的最大特点的支持随机访问

访问元素、改变元素的时间复杂度为 O1

在尾部插入、删除元素的时间复杂度也是 O1

普通情况下插入、删除元素的时间复杂度为 On

重点

  • 数组：二分查找
  • 数组：移除元素
  • 数组：有序数组的平方
  • 数组：长度最小的子数组
  • 数组：螺旋矩阵 II

数组初始化

foo = [0]*5
bar = [0 for _ in range(100)]

数组遍历

# 通过索引遍历数组
for i in range(len(arr)):
    print(arr[i])

数组查找

# 在数组中查找指定元素
def find(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

1. 两数之和open in new window

两数之和 【哈希表】
class Solution:
    def twoSum(self, nums, target):
        temp = dict()
        for i, num in enumerate(nums):
            if target - num in temp:
                return [temp[target - num], i]
            temp[nums[i]] = i
        return []

11. 盛最多水的容器open in new window 💯

盛最多水的容器 【双指针】
class Solution:
    def maxArea(self, height):
        left = 0
        right = len(height) - 1
        ans = 0
        while left < right:
            area = min(height[left], height[right]) * (right - left)
            ans = max(ans, area)
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return ans

15. 三数之和open in new window

15. 三数之和 【哈希】

18. 四数之和open in new window

18. 四数之和 【哈希】

26. 删除有序数组中的重复项open in new window

删除有序数组中的重复项 【快慢指针】
# 快慢指针，快的先走，比较快的位置和慢的位置的值，如果不相等，快的位置赋值给 slow，然后 slow 往前走

# 当快的走完数组之后，nums[:slow] 就是整个数组去重之后的结果了

class Solution:
    def removeDuplicates(self, nums):
        if not nums:
            return 0
        slow = 1
        fast = 1
        n = len(nums)
        while fast < n:
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

27. 移除元素open in new window

移除元素 【快慢指针】
class Solution:
    def removeElement(self, nums, val: int) -> int:
        slow = 0
        fast = 0
        n = len(nums)
        while fast < n:
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

34. 在排序数组中查找元素的第一个和最后一个位置open in new window

在排序数组中查找元素的第一个和最后一个位置 【二分】
class Solution:
    def searchRange(self, nums, target):
        def binarySearch(nums, target):
            left = 0
            right = len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1
            return left
        left_idx = binarySearch(nums, target)
        right_idx = binarySearch(nums, target + 1) - 1
        if left_idx == len(nums) or nums[left_idx] != target:
            return [-1, -1]
        return [left_idx, right_idx]

35. 搜索插入位置open in new window

搜索插入位置 【二分】
class Solution:
    def searchInsert(self, nums, target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left += 1
            else:
                right -= 1
        return left

59. 螺旋矩阵 IIopen in new window

59. 螺旋矩阵 II
class Solution:
    def generateMatrix(self, n: int):
        res = [[0] * n for _ in range(n)]
        left = 0
        right = n - 1
        top = 0
        bottom = n - 1
        num = 1
        while left <= right and top <= bottom:
            for col in range(left, right + 1):
                res[top][col] = num
                num += 1
            for row in range(top + 1, bottom + 1):
                res[row][right] = num
                num += 1
            if left < right and top < bottom:
                for col in range(right - 1, left, -1):
                    res[bottom][col] = num
                    num += 1
                for row in range(bottom, top, -1):
                    res[row][left] = num
                    num += 1
            left += 1
            right -= 1
            top += 1
            bottom -= 1
        return res

80. 删除有序数组中的重复项 IIopen in new window

删除有序数组中的重复项 II【快慢指针】
class Solution:
    def removeDuplicates(self, nums):
        n = len(nums)
        if n < 2:
            return n
        slow = 2
        fast = 2
        while fast < n:
            if nums[fast] != nums[slow - 2]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

136. 只出现一次的数字open in new window

136. 只出现一次的数字 【位运算】
class Solution:
    def singleNumber(self, nums) -> int:
        res = 0
        for i in nums:
            res = res ^ i
        return res

167. 两数之和 II - 输入有序数组open in new window

两数之和 II - 输入有序数组 【左右指针】
class Solution:
    def twoSum(self, numbers, target):
        left = 0
        right = len(numbers) - 1
        while left < right:
            sum = numbers[left] + numbers[right]
            if sum == target:
                return [left + 1, right + 1]
            elif sum < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]

189. 轮转数组open in new window

209. 长度最小的子数组open in new window

长度最小的子数组 【滑动窗口】
class Solution:
    def minSubArrayLen(self, target: int, nums) -> int:
        res = float("inf")
        start = 0  # 滑动窗口起始位置
        total = 0  # 滑动窗口数值之和
        for end in range(len(nums)):
            total += nums[end]
            while total >= target:
                res = min(res, end - start + 1)
                total -= nums[start]
                start += 1
        return 0 if res == float("inf") else res

    def minSubArrayLen2(self, target: int, nums) -> int:
        start = 0
        end = 0
        total = 0
        n = len(nums)
        ans = n + 1
        while end < n:
            total += nums[end]
            while total >= target:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans == n + 1 else ans

240. 搜索二维矩阵 IIopen in new window

搜索二维矩阵 II 【二分】
import bisect


class Solution:
    def searchMatrix(self, matrix, target: int) -> bool:
        def search(nums, target):
            left = 0
            right = len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right -= 1
                else:
                    left += 1
            return -1

        for row in matrix:
            idx = search(row, target)
            if idx >= 0:
                return True
        return False

283. 移动零open in new window

移动零
class Solution:
    def moveZeroes(self, nums) -> None:
        if not nums:
            return
        j = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[j] = nums[i]
                j += 1

        for x in range(j, len(nums)):
            nums[x] = 0

704. 二分查找open in new window 💯

二分查找 【二分】
class Solution:
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (right + left) // 2
            val = nums[mid]
            if val == target:
                return mid
            elif val > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

977. 有序数组的平方open in new window

有序数组的平方 【双指针】
class Solution:
    def sortedSquares(self, nums):
        n = len(nums)
        left = 0
        right = n - 1
        pos = n - 1
        res = [0] * n
        while left <= right:
            if nums[left] * nums[left] > nums[right] * nums[right]:
                res[pos] = nums[left] * nums[left]
                left += 1
            else:
                res[pos] = nums[right] * nums[right]
                right -= 1
            pos -= 1
        return res
上次更新:
贡献者: kongzZ