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

目录

题目链接：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）修改数组，移除所有重复超过两次的元素，并返回剩余元素（即不重复或只重复一次）的数量。这里有一点小误解，因为通常“移除重复项”的表述可能意味着删除所有重复项，只保留唯一的元素，但这段代码实际上是保留最多两次出现的元素。

具体实现思路如下：

1. 初始化指针：使用两个指针（或在这个例子中的索引变量）来遍历数组。一个指针（或索引）change用于跟踪当前应该放置新元素（即不重复或只重复一次的元素）的位置，另一个指针（或索引）findToChange用于遍历整个数组以查找下一个可能的新元素。

2. 遍历数组：通过循环遍历数组（从第二个元素开始，因为第一个元素总是可以被视为“新元素”），比较findToChange指向的元素与findToChange - 1指向的元素是否相等。

3. 比较与替换：

   • 如果不相等，说明找到了一个新的元素（或该元素尚未达到两次出现），则将其复制到change指向的位置，并将change和findToChange都向前移动一位，以便继续查找下一个新元素。
   • 如果相等，说明当前元素是重复的，且前一个元素与它相同，因此不需要将其复制到新位置。只需将findToChange向前移动一位，以继续检查下一个元素。

4. 返回结果：当遍历完整个数组后，change指针（或索引）将指向最后一个新元素之后的位置，即数组应该被截断的位置。因此，change的值（作为索引）就是移除重复项后数组的新长度。

5. 注意：虽然这段代码没有显式地“删除”或“移除”任何元素，但它通过覆盖重复元素并返回新长度的方式，在逻辑上实现了移除重复项的效果。如果需要物理上从数组中删除元素，那么可能需要使用支持动态大小调整的容器（如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 r
            if(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

原文地址：https://blog.csdn.net/DDDDWJDDDD/article/details/142366872

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！