用Rust🦀写算法-数组篇-移除元素

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

1
2
3
4
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

1
2
3
4
5
6
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

💡 思路：

  1. 暴力破解，两层循环，一层判断时候相等，一层将后续元素前移
  2. 双指针法，快指针筛选数据，慢指针记录位置，一层循环搞定

代码（暴力破解）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
         let mut size = nums.len();
         let mut i = 0;
    
         while i < size {
            if nums[i] == val {
                for j in i + 1..size {
                    nums[j - 1] = nums[j];
                }
                size -= 1;
            } else {
                i += 1;
            }
        }
    
        size as i32
    }
}

代码（双指针法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> usize {
        let mut slow = 0;

        for fast in 0..nums.len(){
            if nums[fast] != val{
                nums[slow] = nums[fast];
                slow += 1;
            }
        }

        slow
    }
}

26. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

1
2
3
4
5
6
7
8
9
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度2 ，并且原数组nums的前两个元素被修改为1,2。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度5 ， 并且原数组nums的前五个元素被修改为0,1,2,3,4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • 104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列

💡 思路：

  1. 双指针法，判断快慢指针是否相同，相同时快指针+1，不同时将下标为快指针的元素赋值给下标为慢指针+1的元素，且慢指针+1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let mut slow = 0;

        for fast in 1..nums.len(){
            if nums[fast] == nums[slow]{
                continue;
            }else{
		            slow += 1;
                nums[slow] = nums[fast];
            }
        }
        slow as i32 + 1 //返回的是数组长度 slow为下标
    }
}

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
输入: nums =[0,1,0,3,12]输出:[1,3,12,0,0]

示例 2:

1
输入: nums =[0]输出:[0]

提示:

  • 1 <= nums.length <= 104
  • 231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

💡 思路：

  1. 将nums当成栈，当num不为0时计数，并将其放到计数位，最后在末尾添加0
  2. 快慢指针，当fast指向的数不为0，且fast ≠ slow时 和slow交换

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut stack_size = 0;
        for i in 0..nums.len() {
            if nums[i] != 0 {
                nums[stack_size] = nums[i];
                stack_size += 1;
            }
        }
        nums[stack_size..].fill(0);
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut slow = 0;

        for fast in 0..nums.len() {
            if nums[fast] != 0 {
                if fast != slow{
                    nums.swap(fast, slow);
                }
                slow += 1;
            }
        }
    }
}

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

1
2
3
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

1
2
3
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

1
2
3
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

进阶：

  • 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

💡 思路：

  1. 栈，遇到 ‘#’ 出栈，其他字符进栈，利用栈先进后出的特性获取结果 最后比较
  2. 指针判断有效字符 直接比较

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        fn process_string(s: &str) -> Vec<char> {
            let mut stack = Vec::new();
            for c in s.chars() {
                if c == '#' {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
            stack
        }
        
        process_string(&s) == process_string(&t)
    }
}

代码（思路二）：

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
impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        let (mut i, mut j) = (s.len() as i32 - 1, t.len() as i32 -1);
        let (mut skip_s, mut skip_t) = (0, 0);
        let (s, t) = (s.as_bytes(), t.as_bytes());

        // 根据下标处理字符串
        while i >= 0 || j >= 0 {
            // 处理s 从后往前获取有效字符
            while i >= 0 {
                if s[i as usize] == b'#' {
                    skip_s += 1; // 添加退格符
                    i -= 1;
                } else if skip_s > 0{
                    skip_s -= 1; // 消耗退格符
                    i -= 1;
                } else {
                    break;
                }
            }

            // 处理t 从后往前获取有效字符
            while j >= 0 {
                if t[j as usize] == b'#' {
                    skip_t += 1; // 添加退格符
                    j -= 1;
                } else if skip_t > 0{
                    skip_t -= 1; // 消耗退格符
                    j -= 1;
                } else {
                    break;
                }
            }

            // 不知道这时是因为找到有效字符 还是因为i，j小于0推出循环 所以这里进行判断
            match (i >= 0, j >= 0) {
                (true, true) => if s[i as usize] != t[j as usize] { return false },// 判断有效字符是否相等
                (true, false) | (false, true) => return false,// 长度不一致
                _ => (),
            }

            //有效字符相等 -1进行前面字符判断
            i -= 1;
            j -= 1;
        }

        true
    }
}

注意：
i，j的类型需要为i32，s.len()返回uszie这里需要强转，因为i，j判断 ≥ 0，在uszie上进行-1操作也不会获得小于0的数而是获得uszie.MAX

977. 有序数组的平方

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

示例 1：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

1
2
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • 104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

💡 思路：

  1. 直接平方处理，然后排序
  2. 思路一没有利用到nums非递减顺序条件，以0作为分界点，左边平方后递减，右边平方后递增，使用两个指针，归并两个部分
  3. 直接双指针从数组两边向中间开始比较，并放入新数组

代码（思路一）：

1
2
3
4
5
6
7
impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut nums: Vec<i32> = nums.iter().map(|&num| num * num).collect();
        nums.sort();
        nums
    }
}

代码（思路二）：

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
use std::cmp::Ordering;

impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        // 找到第一个非负数的位置
        let pivot = nums.iter().position(|&x| x >= 0).unwrap_or(n);
        
        // 提前计算平方，避免重复计算
        let squared: Vec<i32> = nums.iter().map(|x| x * x).collect();
        
        // 全为非负数（直接返回平方）
        if pivot == 0 {
            return squared;
        }
        // 全为负数（反转平方数组）
        if pivot == n {
            let mut reversed = squared;
            reversed.reverse();
            return reversed;
        }

        let mut left = pivot as i32 - 1;  // 最后一个负数的位置
        let mut right = pivot as i32;     // 第一个非负数的位置
        let mut result = Vec::with_capacity(n);

        // 归并排序
        while left >= 0 && right < n as i32 {
            match squared[left as usize].cmp(&squared[right as usize]) {
                Ordering::Less => {
                    result.push(squared[left as usize]);
                    left -= 1;
                }
                Ordering::Greater => {
                    result.push(squared[right as usize]);
                    right += 1;
                }
                Ordering::Equal => {
                    result.push(squared[left as usize]);
                    result.push(squared[right as usize]);
                    left -= 1;
                    right += 1;
                }
            }
        }

        // 处理剩余部分
        while left >= 0 {
            result.push(squared[left as usize]);
            left -= 1;
        }
        while right < n as i32 {
            result.push(squared[right as usize]);
            right += 1;
        }

        result
    }
}

代码（思路三）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
		    let n = nums.len();
		    let mut result = vec![0; n];
		    let (mut left, mut right) = (0, n - 1);
		    
		    // 逆序 因为是平方后排序，所以大的数都在两边，比较后将较大的放入到result末尾，重复这个过程
		    for i in (0..n).rev() { 
		        if nums[left].abs() > nums[right].abs() {
		            result[i] = nums[left] * nums[left];
		            left += 1;
				    } else {
		            result[i] = nums[right] * nums[right];
		            right -= 1;
		        }
		    }
		    result
		}
}