当前位置：首页 > news >正文

面试经典150题——删除有序数组中的重复项

news 来源：原创 2024/9/22 5:33:36

题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

题目描述

判题标准:

示例

提示：

解法一：双指针

Java写法：

运行时间

C++写法：

运行时间

论屎山代码是如何出现的

时间复杂度和空间复杂度

总结

题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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

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

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

判题标准:

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

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：

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

示例 2：

输入：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 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非严格递增 排列

解法一：双指针

在给定的整数数组（或在这个例子中是std::vector<int>）中移除重复项，使得每个元素最多只出现两次，并返回移除重复项后数组的新长度（即不包含被移除元素的部分）。不过，根据代码的实际逻辑，它实际上是在原地（in-place）修改数组，移除所有重复超过两次的元素，并返回剩余元素（即不重复或只重复一次）的数量。这里有一点小误解，因为通常“移除重复项”的表述可能意味着删除所有重复项，只保留唯一的元素，但这段代码实际上是保留最多两次出现的元素。

具体实现思路如下：

初始化指针：使用两个指针（或在这个例子中的索引变量）来遍历数组。一个指针（或索引）change用于跟踪当前应该放置新元素（即不重复或只重复一次的元素）的位置，另一个指针（或索引）findToChange用于遍历整个数组以查找下一个可能的新元素。
遍历数组：通过循环遍历数组（从第二个元素开始，因为第一个元素总是可以被视为“新元素”），比较findToChange指向的元素与findToChange - 1指向的元素是否相等。
比较与替换：
- 如果不相等，说明找到了一个新的元素（或该元素尚未达到两次出现），则将其复制到change指向的位置，并将change和findToChange都向前移动一位，以便继续查找下一个新元素。
- 如果相等，说明当前元素是重复的，且前一个元素与它相同，因此不需要将其复制到新位置。只需将findToChange向前移动一位，以继续检查下一个元素。
返回结果：当遍历完整个数组后，change指针（或索引）将指向最后一个新元素之后的位置，即数组应该被截断的位置。因此，change的值（作为索引）就是移除重复项后数组的新长度。
注意：虽然这段代码没有显式地“删除”或“移除”任何元素，但它通过覆盖重复元素并返回新长度的方式，在逻辑上实现了移除重复项的效果。如果需要物理上从数组中删除元素，那么可能需要使用支持动态大小调整的容器（如std::vector），并在最后调用resize方法来截断数组到新的长度。不过，在这个特定的实现中，由于std::vector的大小并未改变，只是返回了一个表示有效元素数量的新长度，因此没有必要进行物理删除。

Java写法：

class Solution {public int removeDuplicates(int[] nums) {int len = nums.length;int change = 1;int findToChange = 1;while(findToChange < len){// 0,0,1,1,1,2,2,3,3,4//   l rif(nums[findToChange] != nums[findToChange - 1]){// 如果前后的值不相等的话就替换一下nums[change] = nums[findToChange];// 赋值完成之后就指针全部后移change++;findToChange++;}else {findToChange++;}}// 最后change指针所在的位置就是合理数组的长度return change;}
}

运行时间

C++写法：

class Solution {  
public:  int removeDuplicates(std::vector<int>& nums) {  int len = nums.size();  int change = 1;  int findToChange = 1;  while (findToChange < len) {  // 检查当前元素是否与前一个元素相等  if (nums[findToChange] != nums[findToChange - 1]) {  // 如果不相等，则将当前元素放到change指针指向的位置  nums[change] = nums[findToChange];  // 指针后移  change++;  }  // 无论是否相等，findToChange都需要后移以检查下一个元素  findToChange++;  }  // 最后change指针所在的位置（也就是下一个应该放置新元素的位置）即为无重复元素数组的长度  return change;  }  
};

运行时间

论屎山代码是如何出现的

class Solution {public int removeDuplicates(int[] nums) {// 获取原数组的长度int len = nums.length;// 定义出指针int change = 1;int findToChange = 1;int resLen = 1;while(findToChange < len && change < len){// 定位好初始的位置if(change == findToChange && nums[change] != nums[change - 1]){change++;findToChange++;resLen++;}else{// change指针就位了if(nums[findToChange] == nums[change]){findToChange++;}else {while(findToChange < len && nums[findToChange - 1] == nums[findToChange]){findToChange++;}if(findToChange < len){// findToChange指针就位了nums[change] = nums[findToChange];change++;findToChange++;resLen++;}}}}return resLen;}
}