Cloud_Player's Notes
0%

LeetCode Day2

发表于 更新于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

LeetCode Day2

数组

移除元素

avatar

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/* 暴力解法 */
/* 注意：不使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组 */
/* 不需要考虑数组中超出新长度后面的元素 */

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        for (int i = 0; i < len; i++)
        {
            int num_i = nums[i]; 
            if (num_i == val) 
            {
                for (int j = i + 1; j < len; j++)
                    nums[j - 1] = nums[j];
                i--; len--;
            } 
        }
        return len;
    }
};

/*
两层for循环
一个for循环遍历数组元素 ，第二个for循环更新数组
时间复杂度 O(n^2)
*/

/* 双指针法（快慢指针法）*/

/*
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
定义快慢指针:
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置
*/

/* 自己写的，也过了 */
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        int slowIndex = 0, fastIndex = 0;
        while(fastIndex < len)
        {
            if(fastIndex != slowIndex) 
                nums[slowIndex] = nums[fastIndex];
            if(nums[slowIndex] == val) slowIndex--;
            fastIndex++;
            slowIndex++;
        }
        return slowIndex;
    }
};

/* 代码随想录中的双指针法标准代码 */
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

/* 理解：
fastIndex 要是指向了一个值为 val 的元素
那么 slowIndex 的自增就得停一次（即代表最后的长度-1）
那如果指向的元素值不为 val，那就无脑把后面的值赋到前面去
结合我自己的理解，可以改一下 if 语句的代码：
if (val != nums[fastIndex]) {
    if (fastIndex != slowIndex) nums[slowIndex] = nums[fastIndex];
    slowIndex++;
}
*/

/**
* 还有一种方法：
* 相向双指针方法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        while (leftIndex <= rightIndex) {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val){
                ++leftIndex;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val) {
                -- rightIndex;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素
    }
};

avatar

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
/* 自己写的，能过 */
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slowIndex = 0, fastIndex = 1;
        int len = nums.size();
        bool flag = false;
        while(fastIndex < len)
        {
            if(nums[fastIndex] != nums[slowIndex])
            {
                slowIndex++;
                if(flag)
                {
                    flag = false;
                    nums[slowIndex] = nums[fastIndex];
                    continue;
                }   
            }
            else flag = true;
            fastIndex++;
        }
        return slowIndex + 1;
    }
};

/*
想法：
首先用一个 flag 区分是不是遇到了重复元素
当遇到了重复元素时，flag = true
如果两个指针指向的元素不相同，并且之前是重复元素
则进行赋值，并且置 flag 为 false
注意，赋值后，人为地制造了重复元素
那么就不让 fastIndex 向后走
重新进入循环，检测出这一次重复
*/

/* 来看看官方题解 */
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        } // 可以删了，规定 n >= 1
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

/*
从下标 1 开始删除元素
对于每个位置，如果 nums[fast] ≠ nums[fast−1]
​说明 nums[fast] 和之前的元素都不同
因此将 nums[fast] 的值复制到 nums[slow]
然后将 slow 的值加 1，即指向下一个位置
*/

/*
标准答案没有我写的那么别扭qwq
它的思路是将整个要解决的问题
变成（用fastIndex）找到之前没有的值放到前面（slowIndex）去
这样就清晰很多
*/