手撕算法：数组

704: 二分法

视频链接： https://www.bilibili.com/video/BV1fA4y1o715/?spm_id_from=333.788&vd_source=f8ee4d4e31e4049864a5ba319b83aea7
力扣704： https://leetcode.cn/problems/binary-search/

要点： 确定区间是左闭右闭还是左闭右开，这决定了之后进行while循环的时候如何选择区间；

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right  = 0, len(nums)-1
        while(left <= right):

            middle = int((left + right)/2)
            
            if (nums[middle] > target):
                right = middle - 1
            elif(nums[middle] < target):
                left = middle + 1
            else:
                return middle
        
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

27： 移除元素（双指针思路）

视频链接： https://www.bilibili.com/video/BV12A4y1Z7LP/?spm_id_from=pageDriver&vd_source=f8ee4d4e31e4049864a5ba319b83aea7
力扣链接：

erase是一个$O(n)$的操作；
并没有真正意义的删除，而只是元素的覆盖而已；
代码很巧妙和简洁：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0 

        for fast  in range(0, len(nums)):
            if (nums[fast] != val):
                nums[slow] = nums[fast]
                slow = slow + 1

        return slow
1
2
3
4
5
6
7
8
9
10

977: 有序数组的平方（双指针解法）

视频链接
力扣链接

暴力解法就是直接平方然后再排序，如果用快排的话，时间复杂度就是$O(nlog(n))$。

这里记录一个时间复杂度为$O(n)$的解法。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        num_size = len(nums)
        res = nums.copy()

        i,j, k = 0, num_size - 1, num_size - 1

        while(i <= j):
            l_square = nums[i] * nums[i]
            r_square = nums[j] * nums[j]

            if ( l_square > r_square):
                res[k] = l_square
                i = i + 1
            else:
                res[k] = r_square
                j = j - 1

            k = k - 1
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21