概述
當處理排序數(shù)組時，刪除重復(fù)元素是一個常見的問題。首先，我們來看一下如何解決這個問題，然后再進一步討論如何處理允許最多重復(fù)兩次的情況。
刪除重復(fù)元素
問題描述：給定一個已排序的數(shù)組，刪除重復(fù)的元素，使得每個元素只出現(xiàn)一次，并返回新的長度。
解決思路：
使用雙指針方法。一個指針用于遍歷數(shù)組，另一個指針指向當前不重復(fù)元素應(yīng)該存放的位置。
通過比較當前元素與前一個元素是否相等，確定是否需要移動元素。
方法：
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;
}
刪除重復(fù)元素（允許最多重復(fù)兩次）
問題描述：給定一個已排序的數(shù)組，刪除重復(fù)的元素，使得每個元素最多只出現(xiàn)兩次，并返回新的長度。
解決思路：
仍然使用雙指針方法，但需要進行一些額外的判斷。
使用一個計數(shù)器來記錄當前元素的重復(fù)次數(shù)，控制重復(fù)次數(shù)不超過兩次。由于代碼本身已經(jīng)排序，所以只需要使用一個計數(shù)器，否則需要使用哈希表
解決方法：
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;
}
如果數(shù)組無序
如果數(shù)組不是有序的，并且要求刪除重復(fù)元素的同時保持原來的順序，可以使用哈希表來解決這個問題。
重復(fù)一次
下面是解決辦法的詳細步驟：
初始化一個空的哈希表來記錄已經(jīng)出現(xiàn)過的元素。
初始化一個新的數(shù)組result，用于存放不重復(fù)的元素。
遍歷原始數(shù)組，對于每個元素：
如果該元素不在哈希表中，表示遇到了一個新的不重復(fù)元素。將其添加到哈希表中，并將其添加到result數(shù)組末尾。
如果該元素已經(jīng)在哈希表中，表示遇到了重復(fù)元素，直接跳過該元素。
返回result數(shù)組的長度作為結(jié)果。
以下是使用C++實現(xiàn)的代碼示例：
#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; // 更新原數(shù)組為不重復(fù)的結(jié)果數(shù)組
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;
}
通過調(diào)用removeDuplicates函數(shù)，可以得到去除重復(fù)元素后的新數(shù)組長度。原數(shù)組nums會被更新為只包含不重復(fù)元素的結(jié)果數(shù)組。代碼中使用了unordered_set來記錄已經(jīng)出現(xiàn)過的元素，保證了查找的時間復(fù)雜度為O(1)。
重復(fù)兩次
可以使用unordered_map來記錄每個元素的出現(xiàn)次數(shù)，以實現(xiàn)刪除重復(fù)元素并保持原始順序的要求。
下面是使用unordered_map解決問題的思路和代碼：
初始化一個空的unordered_map，用于記錄每個元素的出現(xiàn)次數(shù)。
初始化一個新的數(shù)組result，用于存放不重復(fù)的元素。
遍歷原始數(shù)組，對于每個元素：
如果該元素不在unordered_map中，表示遇到了一個新的元素。將其添加到unordered_map中，并將其添加到result數(shù)組末尾。
如果該元素已經(jīng)在unordered_map中，表示遇到了重復(fù)元素。檢查該元素的出現(xiàn)次數(shù)：
如果出現(xiàn)次數(shù)小于2，將其添加到unordered_map中，并將其添加到result數(shù)組末尾。
如果出現(xiàn)次數(shù)大于等于2，直接跳過該元素。
返回result數(shù)組的長度作為結(jié)果。
以下是使用C++實現(xiàn)的代碼示例：
#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; // 更新原數(shù)組為不重復(fù)的結(jié)果數(shù)組
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;
}
通過調(diào)用removeDuplicates函數(shù)，可以得到去除重復(fù)元素后的新數(shù)組長度。原數(shù)組nums會被更新為只包含不重復(fù)元素的結(jié)果數(shù)組。在代碼中，使用unordered_map來記錄每個元素的出現(xiàn)次數(shù)，并根據(jù)出現(xiàn)次數(shù)的大小判斷是否添加到結(jié)果數(shù)組中。文章來源：http://www.zghlxwxcb.cn/news/detail-540450.html
總結(jié)
以上是使用C++實現(xiàn)的解決方案。這兩個問題都可以通過這些代碼解決，并且時間復(fù)雜度為O(n)，其中n是數(shù)組的長度。
希望這篇博文對初學者有所幫助，并能夠清晰地解釋了解決這兩個問題的思路和方法。文章來源地址http://www.zghlxwxcb.cn/news/detail-540450.html
到了這里，關(guān)于力扣刷題：刪除重復(fù)元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
