目录
题目链接: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;}
}
虽然也是过了,但是想的实在是复杂的要死,这种就是一开始没想明白就开始写,然后发现BUG,改BUG,代码屎山就是这样来的。
时间复杂度和空间复杂度
总结
想好再写,先狠狠的思考一波再写兄弟们,不然容易整出屎山代码哦shift