zhouzhou🥣️

数组

发表于 更新于 分类于 阅读次数：
本文字数： 1.1k 阅读时长 ≈ 1 分钟
刷题之数组篇

数组

二分查找

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

示例：

1
2
输入: nums = [-1,0,3,5,9,12], target = 9       
输出: 4           
1
2
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1
二分查找的条件：数组是有序且数组中无重复元素。如果数组有重复的元素，则二分查找返回的元素下标就不是唯一的。

二分法的区间：区间需要遵循循环不变量原则，二分法的区间定义一般有两种：左闭右闭[left, right]和左闭右开[left, right]。

区别：
- 左闭右闭时target可能是nums[left]或者nums[right[，当left = right时，则nums[left] = nums[right] = nums[middle] = target。所以在这种情况下left是可以等于right的, while(left <= right)
且:
nums[middle] > target 时 left 不变 right = middle-1因为 nums[middle] ！= target。
同理nums[middle] < target时right 不变 left = middle +1.

  • 左闭右开时，target 不可能等于 nums[right], 所以 while(right<left)
    且：
    nums[middle] > target 时 left 不变 right = middle
    但当nums[middle] < target时right 不变 left = middle +1.

下面是python代码： [left, right] 

1
2
3
4
5
6
7
8
9
10
11
12
13
def search(nums: list, target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while(left <= right):
        middle = (left + right) // 2
        if(nums[middle] > target):
            right = middle - 1
        elif(nums[middle < target]):
            left = middle + 1
        else:
            return middle
    return -1

[left, right) 
1
2
3
4
5
6
7
8
9
10
11
12
13
def search(nums: list, target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while(left < right):
        middle = (left + right) // 2
        if(nums[middle] > target):
            right = middle
        elif(nums[middle < target]):
            left = middle + 1
        else:
            return middle
    return -1

例子： 

1
2
nums = [-1,0,3,5,9,12]
search(nums, 0)
[left, right]： 
1
2
3
4
nums: [-1, 0, 3, 5, 9, 12]
left: 0 right: 5 middle: 2
left: 0 right: 1 middle: 0
left: 1 right: 1 middle: 1
[left, right): 
1
2
3
nums: [-1, 0, 3, 5, 9, 12]
left: 0 right: 5 middle: 2
left: 0 right: 2 middle: 1

移除元素

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

不要使用额外的数组空间，你必须仅使用 \(O(1)\) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 

1
给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 
1
给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。你不需要考虑数组中超出新长度后面的元素。
两种解法：
1. 暴力解法双指针
2. 快慢指针法

暴力解法：

双循环一个循环遍历数组，第二个循环更新数组。

暴力解法
from:代码随想录 
1
2
3
4
5
6
7
8
9
10
11
def removeVal(nums: list, val: int)-> int:
    size = len(nums)
    i = 0
    while(i < size):
        if nums[i] == val:
            for j in range(i, size-1):
                nums[j] = nums[j+1]
            size = size - 1
        else:
            i = i + 1
    return size

执行步骤：
nums = [3, 2, 2, 3]
val = 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
round 1:
[3, 2, 2, 3]
 ^
the current element is the value! remove it
Now the nums change into: [2, 2, 3, 3]
size now is: 3
---------------------
round 2:
[2, 2, 3, 3]
 ^
---------------------
round 3:
[2, 2, 3, 3]
    ^
---------------------
round 4:
[2, 2, 3, 3]
       ^
the current element is the value! remove it
Now the nums change into: [2, 2, 3, 3]
size now is: 2
---------------------
finished!
时间复杂度: \(O(n^{2})\)
空间复杂度: \(O(1)\)

快慢指针解法

快指针：用来寻找不等于val的元素
慢指针：用来记录新数组的下标
双指针一开始会同时移动，当遇到val元素时，慢指针在该元素停止，快指针继续向前寻找非val的元素，找到时，慢指针处的元素为更新快指针的元素，两个指针继续同时移动。

双指针解法
from:代码随想录 
1
2
3
4
5
6
7
8
9
10
11
def removeVal(nums: list, val: int)-> int:
    fast = 0
    slow = 0
    while(fast < len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow = slow + 1
            fast = fast + 1
        else:
            fast = fast + 1
    return slow

例子：
nums = [0, 1, 2, 2, 3, 0, 4, 2, 3]
val = 2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
----------ROUND 0-----------
fast
 v
[0, 1, 2, 2, 3, 0, 4, 2, 3]
 ^
slow
----------ROUND 1-----------
   fast
    v
[0, 1, 2, 2, 3, 0, 4, 2, 3]
    ^
   slow
----------ROUND 2-----------
      fast
       v
[0, 1, 2, 2, 3, 0, 4, 2, 3]
       ^
      slow

*******FIND THE VAL!*******

----------ROUND 3-----------
         fast
          v
[0, 1, 2, 2, 3, 0, 4, 2, 3]
       ^
      slow

*******FIND THE VAL!*******

----------ROUND 4-----------
            fast
             v
[0, 1, 2, 2, 3, 0, 4, 2, 3]
       ^
      slow

*******NUMS UPDATE!*******

            fast
             v
[0, 1, 3, 2, 3, 0, 4, 2, 3]
       ^
----------ROUND 5-----------
               fast
                v
[0, 1, 3, 2, 3, 0, 4, 2, 3]
          ^
         slow

*******NUMS UPDATE!*******

               fast
                v
[0, 1, 3, 0, 3, 0, 4, 2, 3]
          ^
----------ROUND 6-----------
                  fast
                   v
[0, 1, 3, 0, 3, 0, 4, 2, 3]
             ^
            slow

*******NUMS UPDATE!*******

                  fast
                   v
[0, 1, 3, 0, 4, 0, 4, 2, 3]
             ^
----------ROUND 7-----------
                     fast
                      v
[0, 1, 3, 0, 4, 0, 4, 2, 3]
                ^
               slow

*******FIND THE VAL!*******

----------ROUND 8-----------
                        fast
                         v
[0, 1, 3, 0, 4, 0, 4, 2, 3]
                ^
               slow

*******NUMS UPDATE!*******

                        fast
                         v
[0, 1, 3, 0, 4, 3, 4, 2, 3]
                ^
Finished!
Return: 6