[数据结构与算法]数组部分算法题（代码随想录）

数组

1.二分查找

题目链接

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

左闭右闭

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i,j = 0,len(nums)-1
        while i <= j: # [i,j] i==j 在这个区间范围内
            m = i+ ((j-i) >> 1) # 等同于(i+j)>>1 防止 i+j溢出
            if nums[m] > target:
                j = m-1
            elif nums[m] < target:
                i = m+1
            else:
                return m
        return -1

一定要遵循循环不变量规则(坚持根据区间的定义来操作)

左闭右开

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # [i,j)  j不能为len(nums)-1
        i,j = 0,len(nums)
        while i < j: # [i,j)
            m = i + ((j - i) >> 1)
            if nums[m] > target:
                j = m
            elif nums[m] < target:
                i = m+1
            else:
                return m
        return -1

2.移除元素

题目链接

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

自己的思路实现

来两个指针i，j i指向数组头部，j指向数组尾部；先遍历头部，遇到val，就遍历尾部，不是val，置换到i的位置，继续遍历i。直到i > j。

def removeElement(self, nums: List[int], val: int) -> int:
    i,j,cur = 0,len(nums) - 1,0
    while i <= j:
        if cur == i and cur!=j:
            if nums[cur] != val:
                i = i+1
                cur = i
            else:
                cur = j
        else:
            if nums[cur] != val:
                nums[i] = nums[cur]
                j = j-1
                cur = i
            else:
                j = j-1
                cur = j
    return cur+1

def removeElement(self, nums: List[int], val: int) -> int:
    i,j = 0,len(nums) - 1
    while i <= j:
        while i <= j and nums[i] != val:
            i += 1
        while i <= j and nums[j] == val:
            j -= 1
        if i < j:
            nums[i] = nums[j]
            i += 1
            j -= 1
    return i

快慢指针

思路很简单，就是没想到

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

def removeElement(self, nums: List[int], val: int) -> int:
    slow,fast = 0,0
    for fast in range(0,len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow = slow + 1
        fast = fast + 1
    return slow

3.有序数组的平方

题目链接

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

def sortedSquares(self, nums: List[int]) -> List[int]:
    n = len(nums)
    if n == 0 or nums is None:
        return
    i,j,k = 0,n - 1,n - 1
    result = [-1]*n
    while i <= j:
        if abs(nums[i]) > abs(nums[j]):
            result[k] = abs(nums[i]) ** 2
            i += 1
        else:
            result[k] = abs(nums[j]) ** 2
            j -= 1
            k -= 1

    return result

4.长度最小的子数组(2)

题目链接

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

滑动窗口 前缀和 双指针

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n = len(nums)
    i,j,sum,result = 0,0,0,100001

    while j < n:
        sum += nums[j]
        while sum >= target:
            result = min(result, j - i + 1)
            sum -= nums[i]
            i += 1
        j += 1
    if result == 100001:
        return 0
    return result

5.螺旋矩阵II

题目链接

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

自己Kill的，nice!!

def generateMatrix(self, n: int) -> List[List[int]]:
    array = [[0 for i in range(n)] for j in range(n)]
    d = [[0,1],[1,0],[0,-1],[-1,0]]
    mod = 0
    i,j = 0,0
    array[i][j] = 1
    for k in range(1,n ** 2):
        ii = i + d[mod][0]
        jj = j + d[mod][1]
        if 0 <= ii < n and 0 <= jj < n and array[ii][jj] == 0:
            array[ii][jj] = k + 1
        else:
            mod = (mod + 1) % 4
            ii = i + d[mod][0]
            jj = j + d[mod][1]
            array[ii][jj] = k + 1
        i = ii
        j = jj

    return array

总结