代码随想录算法训练营第一天| 704. 二分查找、35.搜索插入位置、27. 移除元素、977.有序数组的平方

文档讲解：代码随想录

视频讲解：代码随想录

状态：完成4道题

一、数组理论基础

数组：连续内存空间，存储类型相同的元素集合，适合读不适合写

注意：Python里可以存储不同类型的元素，但刷题时都是按照相同元素去做的相同元素占用存储的空间大小是一样的，下一个元素的位置就确定了

数组时间复杂度：

访问：可以通过索引直接访问，时间复杂度为O(1)

搜索：需要从头开始查找，时间复杂度为O(N)

插入：找到指定元素这里的时间复杂度为O(1) ，为了保证内存空间的连续性，需要把后续的元素往后挪动，所以时间复杂度为O(N)，但在最后一个元素的尾部插入，时间复杂度为O(1)

删除：找到指定元素这里的时间复杂度为O(1) ，为了保证内存空间的连续性， 需要把后续的元素往前挪动，所以时间复杂度为O(N)，但删除最后一个元素，时间复杂度为O(1)。（注意：在做题时要注意数组的元素是不能删的，只能覆盖）

综上所述：Python里默认的插入、删除会操作最后一个元素，因为时间复杂度为O(1)

二、数组相关题型

704.二分查找

左闭右闭[left,right]

def search(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        m = (left + right) // 2
        if nums[m] > target:
            right = m-1
        elif nums[m] < target:
            left = m+1
        else:
            return m
    return -1

左闭右开[left,right)

def search(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        m = (left + right) // 2
        if nums[m] > target:
            right = m
        elif nums[m] < target:
            left = m + 1
        else:
            return m
    return -1

35.搜索插入位置

同样是二分法

左闭右闭[left,right]

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

左闭右开[left,right)

def searchInsert(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            right = mid
        else:
            left = mid + 1
    return left

27.移除元素

错误示例：当nums=[2,2] val=2时，删除第一个值后，后面的元素会移动到前面去，即索引变了，导致输出的结果为nums=[2]，长度为1

因为数组是连续的只能覆盖不能直接删除

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        for i in nums:
            if val == i:
                nums.remove(i)
        return len(nums)

双指针（快慢指针）思路：

两个指针，前面一个后面一个，前面的用于搜索需要删除的值，当遇到需要删除的值时，前指针直接跳过，后面的指针不动，当遇到正常值时，两个指针都进行移动，并修改慢指针的值。最后只需输出慢指针的索引即可。

Python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        solw,fast = 0,0
        while fast < len(nums):
            if val == nums[fast]:
                fast +=1
            else:
                nums[solw] =nums[fast]
                fast +=1
               solw +=1
        return solw

Java 

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

977.有序数组的平方

暴力解

def sortedSquares(nums):
    res = []
    for i in nums:
        i = i * i
        res.append(i)
    res.sort()
    return res

双指针（碰撞指针）思路：

因为是求每个数字的平方，平方后的最大值在数组两侧，靠近中间的值最小，最后按非递减顺序排序，所以使用双指针，放在数组两侧，比较平方后的大小。最后将结果按顺序放入新的数组中去。

def sortedSquares(nums):
    l = 0  # nums数组的左指针
    r = len(nums) - 1  # nums数组的右指针
    i = len(nums) - 1  # res新数组指针，从右向左开始遍历
    res = [float('inf')] * len(nums)  # 定义新数组，用来存放结果
    while l <= r:
        if nums[l] ** 2 < nums[r] ** 2:  # 左右边界进行对比，找出最大值
            res[i] = nums[r] ** 2
            r -= 1  # 右指针往左移动
        else:
            res[i] = nums[l] ** 2
            l += 1  # 左指针往右移动
        i -= 1  # 存放结果的指针需要往前平移一位
    return res