商业网站后缀名_美国免费网站服务器下载_互联网广告管理暂行办法_怎么建个人网站

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

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

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

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

用户评测：

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

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];
}

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

二、解题思路

为了解决这个问题，我们可以使用 双指针 技巧。一个指针遍历整个数组，另一个指针记录不等于 val 的元素的位置。通过这样的方式，我们可以原地修改数组并将等于 val 的元素“移除”。

• 初始化指针：
  • 使用一个指针 i 遍历整个数组，另一个指针 k 用来记录下一个存储不等于 val 的元素的位置。
• 遍历数组：
  • 遍历 nums 数组的每个元素，如果 nums[i] != val，将 nums[i] 赋值给 nums[k]，并将 k 向右移动一位。
  • 如果 nums[i] == val，跳过该元素。
• 结束条件：
  • 当遍历完整个数组后，指针 k 就是不等于 val 的元素的数量，并且 nums 数组的前 k 个位置已经被修改为不等于 val 的元素。

三、代码

class Solution {public int removeElement(int[] nums, int val) {// 初始化指针 k 记录不等于 val 的元素位置int k = 0;// 遍历数组for (int i = 0; i < nums.length; i++) {// 如果当前元素不等于 valif (nums[i] != val) {// 将其放置在 k 的位置，并移动 knums[k] = nums[i];k++;}}// 返回不等于 val 的元素的数量 kreturn k;}
}

四、复杂度分析

时间复杂度：

• O(n)：我们遍历了一遍数组，其中 n 是数组的长度。

空间复杂度：

• O(1)：我们只使用了常数级别的额外空间，直接在原数组上进行修改。