力扣刷题：删除重复元素-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣刷题：删除重复元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

概述

当处理排序数组时，删除重复元素是一个常见的问题。首先，我们来看一下如何解决这个问题，然后再进一步讨论如何处理允许最多重复两次的情况。

删除重复元素

问题描述：给定一个已排序的数组，删除重复的元素，使得每个元素只出现一次，并返回新的长度。

解决思路：

使用双指针方法。一个指针用于遍历数组，另一个指针指向当前不重复元素应该存放的位置。
通过比较当前元素与前一个元素是否相等，确定是否需要移动元素。

方法：

int removeDuplicates(vector<int>& nums) {
    if (nums.size() <= 1)
        return nums.size();
    
    int index = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[i - 1]) {
            nums[index] = nums[i];
            index++;
        }
    }
    
    return index;
}

删除重复元素（允许最多重复两次）

问题描述：给定一个已排序的数组，删除重复的元素，使得每个元素最多只出现两次，并返回新的长度。

解决思路：

仍然使用双指针方法，但需要进行一些额外的判断。
使用一个计数器来记录当前元素的重复次数，控制重复次数不超过两次。由于代码本身已经排序，所以只需要使用一个计数器，否则需要使用哈希表

解决方法：

int removeDuplicates(vector<int>& nums) {
    if (nums.size() <= 2)
        return nums.size();
    
    int index = 2;
    int count = 1;
    for (int i = 2; i < nums.size(); i++) {
        if (nums[i] != nums[index - 1]) {
            nums[index] = nums[i];
            index++;
            count = 1;
        } else if (count < 2) {
            nums[index] = nums[i];
            index++;
            count++;
        }
    }
    
    return index;
}

如果数组无序

如果数组不是有序的，并且要求删除重复元素的同时保持原来的顺序，可以使用哈希表来解决这个问题。

重复一次

下面是解决办法的详细步骤：

初始化一个空的哈希表来记录已经出现过的元素。
初始化一个新的数组result，用于存放不重复的元素。
遍历原始数组，对于每个元素：
如果该元素不在哈希表中，表示遇到了一个新的不重复元素。将其添加到哈希表中，并将其添加到result数组末尾。
如果该元素已经在哈希表中，表示遇到了重复元素，直接跳过该元素。
返回result数组的长度作为结果。
以下是使用C++实现的代码示例：

#include <iostream>
#include <vector>
#include <unordered_set>

int removeDuplicates(std::vector<int>& nums) {
    std::unordered_set<int> seen;
    std::vector<int> result;
    
    for (int num : nums) {
        if (seen.find(num) == seen.end()) {
            seen.insert(num);
            result.push_back(num);
        }
    }
    
    nums = result;  // 更新原数组为不重复的结果数组
    
    return result.size();
}

int main() {
    std::vector<int> nums = {3, 1, 2, 1, 3, 2, 4};
    
    int length = removeDuplicates(nums);
    
    std::cout << "Length: " << length << std::endl;
    std::cout << "New Array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

通过调用removeDuplicates函数，可以得到去除重复元素后的新数组长度。原数组nums会被更新为只包含不重复元素的结果数组。代码中使用了unordered_set来记录已经出现过的元素，保证了查找的时间复杂度为O(1)。

重复两次

可以使用unordered_map来记录每个元素的出现次数，以实现删除重复元素并保持原始顺序的要求。
下面是使用unordered_map解决问题的思路和代码：
初始化一个空的unordered_map，用于记录每个元素的出现次数。
初始化一个新的数组result，用于存放不重复的元素。
遍历原始数组，对于每个元素：
如果该元素不在unordered_map中，表示遇到了一个新的元素。将其添加到unordered_map中，并将其添加到result数组末尾。
如果该元素已经在unordered_map中，表示遇到了重复元素。检查该元素的出现次数：
如果出现次数小于2，将其添加到unordered_map中，并将其添加到result数组末尾。
如果出现次数大于等于2，直接跳过该元素。
返回result数组的长度作为结果。
以下是使用C++实现的代码示例：

#include <iostream>
#include <vector>
#include <unordered_map>

int removeDuplicates(std::vector<int>& nums) {
    std::unordered_map<int, int> counts;
    std::vector<int> result;
    
    for (int num : nums) {
        if (counts.find(num) == counts.end()) {
            counts[num] = 1;
            result.push_back(num);
        } else {
            if (counts[num] < 2) {
                counts[num]++;
                result.push_back(num);
            }
        }
    }
    
    nums = result;  // 更新原数组为不重复的结果数组
    
    return result.size();
}

int main() {
    std::vector<int> nums = {3, 1, 2, 1, 3, 2, 4};
    
    int length = removeDuplicates(nums);
    
    std::cout << "Length: " << length << std::endl;
    std::cout << "New Array: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}