LeetCode第二十六题：删除有序数组中的重复项

admin
学习
2024-04-01
69热度
0评论

1.题目描述

给你一个 非严格递增排列 的数组 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 。不需要考虑数组中超出新长度后面的元素。

提示：

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

2.解题思路

解法一：双指针法

描述：一个慢指针i，它跟踪当前不重复元素的最后位置；一个快指针j，它用于探索数组前进并发现新的不重复元素。快指针j从数组的第二个元素开始遍历，因为第一个元素总是被视为不重复元素，并且是慢指针i的起始位置。在每一步中，比较快指针j和慢指针i指向的元素。当快指针j遍历完数组时，数组的前i+1个元素是唯一的，并且保持了它们最初的顺序。函数返回i+1，即不重复元素的数量。
时间复杂度：O(n)。
空间复杂度：O(1)。
参考代码：

java版：

class Solution {
    public int removeDuplicates(int[] nums) {
        // 如果数组为空，则直接返回0
        if (nums.length == 0)
            return 0;
        // 初始化慢指针i
        int i = 0;
        // 快指针j开始从1遍历数组
        for (int j = 1; j < nums.length; j++) {
            // 如果找到一个不重复的元素，则将其移动到i的下一个位置
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        // 数组的前i+1个元素是唯一的，返回i+1作为不重复元素的数量
        return i + 1;
    }
}

C++版：

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

// 如果数组为空，则没有需要删除的重复项

if (nums.empty()) return 0;

// 初始化慢指针i为0

int i = 0;

// 使用快指针j遍历数组

for (int j = 1; j < nums.size(); j++) {

// 当遇到一个不重复的元素时

if (nums[i] != nums[j]) {

// 移动慢指针

i++;

// 更新i位置的值为新发现的唯一元素

nums[i] = nums[j];

}

// 返回不重复元素的数量，即i+1

return i + 1;

}

};

C版：

// 去除有序数组中的重复项并返回新的数组长度
int removeDuplicates(int* nums, int numsSize) {
    // 如果数组大小为0或1，直接返回原大小，因为没有或只有一个元素时不可能有重复
    if (numsSize <= 1) return numsSize;

    // 初始化慢指针i为0
    int i = 0;
    // 使用快指针j遍历数组
    for (int j = 1; j < numsSize; j++) {
        // 如果找到不重复的元素
        if (nums[j] != nums[i]) {
            i++; // 移动慢指针
            nums[i] = nums[j]; // 将新发现的唯一元素复制到i的位置
        }
    }
    // 返回不重复元素的数量，即i+1
    return i + 1;
}

解法二：集合法（非原地）

描述：创建一个空集合用于存储遍历过程中遇到的每个唯一元素。逐个检查数组中的每个元素。对于每个元素，将其添加到集合中。如果元素已经存在于集合中，则不会重复添加，从而实现去重。
时间复杂度：O(n)。
空间复杂度：O(n)。
参考代码：

java版：

class Solution {
    public int removeDuplicates(int[] nums) {
        // 使用LinkedHashSet来保持元素的插入顺序
        Set<Integer> set = new LinkedHashSet<>();

        for (int num : nums) {
            set.add(num);
        }
        // 将集合的元素回写到原数组
        int i = 0;
        for (int num : set) {
            nums[i++] = num;
        }
        // 返回唯一元素的数量，即集合的大小
        return set.size();
    }
}

C++版：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 使用set去重
        set<int> s(nums.begin(), nums.end());

        // 将set中的元素写回到原vector中
        int index = 0;
        for (int num : s) {
            nums[index++] = num;
        }

        // 返回去重后的元素数量
        return s.size();
    }
};

C版：

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    // 分配辅助数组
    int* temp = (int*)malloc(numsSize * sizeof(int));
    int i, j = 0;

    // 复制第一个元素
    temp[j++] = nums[0];

    // 遍历原数组
    for (i = 1; i < numsSize; i++) {
        if (nums[i] != nums[i - 1]) {
            // 如果发现新的唯一元素，添加到辅助数组
            temp[j++] = nums[i];
        }
    }

    // 将唯一元素复制回原数组
    memcpy(nums, temp, j * sizeof(int));

    // 释放辅助数组
    free(temp);

    return j;
}