C++數(shù)組去重十種方法
在C++中，數(shù)組去重是一個常見的操作，以下是一些常見的數(shù)組去重方法：
一、使用std::sort和std::unique（STL方法）
原理
首先，
std::sort函數(shù)用于對數(shù)組進行排序。它基于比較操作將數(shù)組元素按特定順序（默認是升序）排列。例如，對于一個整數(shù)數(shù)組int arr[] = {5, 3, 4, 3, 2, 5};，std::sort會將其重新排列為有序的序列，如{2, 3, 3, 4, 5, 5}。然后，
std::unique函數(shù)用于去除相鄰的重復元素。它通過將不重復的元素移動到數(shù)組的前面部分來實現(xiàn)去重。在上面排序后的數(shù)組中，std::unique會將不重復的元素2, 3, 4, 5移動到數(shù)組的前面，返回一個指向去重后數(shù)組末尾的迭代器（實際上是一個指針，在數(shù)組場景下）。
示例代碼：
#include <iostream>
#include <algorithm>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::sort(arr, arr + n);
int new_end = std::unique(arr, arr + n)-arr;
for (int i = 0; i < new_end; i++) {
std::cout << arr[i] << " ";
}
return 0;
}在這個示例中，首先計算數(shù)組的大小，然后對數(shù)組進行排序，接著使用std::unique去重，最后遍歷去重后的數(shù)組部分并輸出。
注意事項
std::unique只能去除相鄰的重復元素，所以在使用之前通常需要先對數(shù)組進行排序。它不會改變數(shù)組的大小，只是將重復的元素移到數(shù)組的末尾部分，返回的是去重后有效元素的末尾位置。
二、使用std::set容器
原理
std::set是C++ STL中的關聯(lián)容器，它的特性是元素唯一。當向std::set中插入元素時，它會自動檢查元素是否已經(jīng)存在，如果不存在則插入，否則忽略。
示例代碼：
#include <iostream>
#include <set>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::set<int> s;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
}
for (auto it = s.begin(); it!= s.end(); it++) {
std::cout << *it << " ";
}
return 0;
}這里首先創(chuàng)建一個std::set，然后遍歷數(shù)組將元素插入到std::set中，最后遍歷std::set輸出去重后的元素。
注意事項
std::set中的元素是按照特定順序存儲的（默認是升序），如果不需要這種順序，可以考慮使用std::unordered_set，它在插入和查找操作上可能會更高效。使用
std::set去重會改變元素的存儲結構，并且如果需要將去重后的結果再轉換回數(shù)組，需要額外的操作。
三、手動比較法（雙循環(huán)法）
原理
這種方法使用兩層循環(huán)。外層循環(huán)遍歷數(shù)組的每個元素，內(nèi)層循環(huán)用于比較當前元素與之前已經(jīng)處理過的元素是否相同。如果找到相同的元素，則說明當前元素是重復的，可以跳過或者進行相應的處理。
示例代碼：
#include <iostream>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int new_size = 0;
for (int i = 0; i < n; i++) {
bool is_duplicate = false;
for (int j = 0; j < new_size; j++) {
if (arr[i] == arr[j]) {
is_duplicate = true;
break;
}
}
if (!is_duplicate) {
arr[new_size] = arr[i];
new_size++;
}
}
for (int i = 0; i < new_size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}在這個示例中，new_size用于記錄去重后的數(shù)組大小。外層循環(huán)每次取一個元素，內(nèi)層循環(huán)檢查該元素是否已經(jīng)在前面出現(xiàn)過，如果沒有則將其放入去重后的數(shù)組部分。
注意事項
這種方法的時間復雜度較高，為O(n^2)O(n2)，其中
n是數(shù)組的大小。當數(shù)組規(guī)模較大時，性能可能會比較差。它不需要額外的容器，但代碼相對復雜一些。
四、利用std::map記錄元素出現(xiàn)次數(shù)
原理
std::map是C++ STL中的關聯(lián)容器，它以鍵 - 值對的形式存儲數(shù)據(jù)。在這里，可以將數(shù)組元素作為鍵，元素出現(xiàn)的次數(shù)作為值。在遍歷數(shù)組時，如果元素第一次出現(xiàn)，則將其插入std::map中，值設為1；如果元素已經(jīng)存在，則將對應的值加1。最后，只遍歷值為1的鍵，即為去重后的元素。
示例代碼：
#include <iostream>
#include <map>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::map<int, int> m;
for (int i = 0; i < n; i++) {
if (m.find(arr[i])!= m.end()) {
m[arr[i]]++;
} else {
m[arr[i]] = 1;
}
}
for (auto it = m.begin(); it!= m.end(); it++) {
if (it->second == 1) {
std::cout << it->first << " ";
}
}
return 0;
}首先創(chuàng)建std::map，然后遍歷數(shù)組更新元素的出現(xiàn)次數(shù)，最后遍歷std::map輸出只出現(xiàn)一次的元素。
注意事項
這種方法使用了額外的
std::map容器來存儲元素的出現(xiàn)次數(shù)信息，會占用一定的額外空間。相比于直接比較的方法，雖然時間復雜度在平均情況下可能較好，但對于一些特殊情況可能會有一定的性能開銷。
五、使用std::unordered_set（哈希表去重）
原理
std::unordered_set是基于哈希表實現(xiàn)的關聯(lián)容器。它的插入和查找操作平均時間復雜度接近常數(shù)時間O(1)O(1)。當向std::unordered_set中插入元素時，它會根據(jù)元素的哈希值快速判斷元素是否已經(jīng)存在，如果不存在則插入，從而實現(xiàn)去重。
示例代碼：
#include <iostream>
#include <unordered_set>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::unordered_set<int> s;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
}
for (auto it = s.begin(); it!= s.end(); it++) {
std::cout << *it << " ";
}
return 0;
}與使用std::set類似，只是這里使用的是std::unordered_set，它在性能上可能更適合一些不需要排序且元素數(shù)量較多的情況。
注意事項
std::unordered_set的哈希函數(shù)可能會導致哈希沖突，在極端情況下可能會影響性能。不過在大多數(shù)情況下，它的性能表現(xiàn)較好。同樣，將去重后的結果轉換回數(shù)組可能需要額外的操作。
六、標記法
原理
可以創(chuàng)建一個額外的布爾類型數(shù)組來標記已經(jīng)出現(xiàn)過的元素。遍歷原始數(shù)組時，對于每個元素，檢查其在標記數(shù)組中的對應位置是否已經(jīng)被標記。如果沒有被標記，則說明該元素是第一次出現(xiàn)，將其加入去重后的結果中，并在標記數(shù)組中標記該元素；如果已經(jīng)被標記，則說明是重復元素，跳過。
示例代碼：
#include <iostream>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
bool marked[n];
for (int i = 0; i < n; i++) {
marked[i] = false;
}
int new_size = 0;
for (int i = 0; i < n; i++) {
if (!marked[i]) {
arr[new_size] = arr[i];
new_size++;
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
marked[j] = true;
}
}
}
}
for (int i = 0; i < new_size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}這里首先初始化標記數(shù)組，然后在遍歷原始數(shù)組時，根據(jù)標記數(shù)組判斷元素是否重復，并更新標記數(shù)組和去重后的數(shù)組。
注意事項
這種方法需要額外創(chuàng)建一個與原始數(shù)組大小相同的布爾類型數(shù)組來進行標記，會占用一定的額外空間。
它的時間復雜度取決于原始數(shù)組中重復元素的分布情況，但在最壞情況下也是O(n^2)O(n2)。
七、排序后單循環(huán)比較（優(yōu)化雙循環(huán)法）
原理
先對數(shù)組進行排序，這樣相同的元素就會相鄰。然后只需要一次循環(huán)遍歷數(shù)組，比較當前元素和下一個元素是否相同。如果不同，則說明當前元素是不重復的，可以進行相應處理；如果相同，則說明是重復元素，可以跳過。
示例代碼:
#include <iostream>
#include <algorithm>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::sort(arr, arr + n);
int new_size = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i]!= arr[i + 1]) {
arr[new_size] = arr[i];
new_size++;
}
}
arr[new_size] = arr[n - 1];
new_size++;
for (int i = 0; i < new_size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}先對數(shù)組排序，然后在循環(huán)中比較相鄰元素，最后將最后一個元素處理并輸出去重后的數(shù)組。
注意事項
相比于普通的雙循環(huán)法，這種方法利用了排序后相同元素相鄰的特性，減少了比較的次數(shù)，時間復雜度為O(nlogn + n)O(nlogn+n)，其中nlognnlogn是排序的時間復雜度，
n是遍歷數(shù)組的時間復雜度。不過它需要先對數(shù)組進行排序，如果不需要排序后的結果，這可能會是一個額外的開銷。
八、利用數(shù)組指針和動態(tài)內(nèi)存分配
原理
可以創(chuàng)建一個動態(tài)分配內(nèi)存的新數(shù)組，然后通過指針遍歷原始數(shù)組。對于原始數(shù)組中的每個元素，檢查它是否已經(jīng)存在于新數(shù)組中。如果不存在，則將其添加到新數(shù)組中。這種方法可以避免使用一些復雜的STL容器，但需要手動管理內(nèi)存。
示例代碼:
#include <iostream>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int* new_arr = new int[n];
int new_size = 0;
for (int i = 0; i < n; i++) {
bool is_duplicate = false;
for (int j = 0; j < new_size; j++) {
if (arr[i] == new_arr[j]) {
is_duplicate = true;
break;
}
}
if (!is_duplicate) {
new_arr[new_size] = arr[i];
new_size++;
}
}
for (int i = 0; i < new_size; i++) {
std::cout << new_arr[i] << " ";
}
delete[] new_arr;
return 0;
}這里動態(tài)分配了一個新數(shù)組，然后通過雙循環(huán)比較將不重復的元素放入新數(shù)組，最后輸出并釋放內(nèi)存。
注意事項
這種方法需要手動管理動態(tài)分配的內(nèi)存，如果忘記釋放內(nèi)存會導致內(nèi)存泄漏。
雙循環(huán)比較導致時間復雜度為O(n^2)O(n2)，性能在數(shù)組較大時可能較差。
九、使用std::vector和std::erase - std::remove組合（針對std::vector類型數(shù)組）
原理
在C++中，std::vector是一個動態(tài)數(shù)組容器。std::remove函數(shù)實際上并不會真正刪除元素，而是將不想要的元素移到容器的末尾，并返回一個指向新的邏輯末尾的迭代器。然后std::erase函數(shù)根據(jù)這個迭代器真正地從std::vector中刪除元素。
示例代碼:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {5, 3, 4, 3, 2, 5};
v.erase(std::remove(v.begin(), v.end(), 3), v.end());
v.erase(std::remove(v.begin(), v.end(), 5), v.end());
for (auto it : v) {
std::cout << it << " ";
}
return 0;
}這里先使用std::remove將指定元素（這里是3和5）移到std::vector的末尾，然后使用std::erase刪除這些元素。需要注意的是，如果要去重所有元素，可能需要多次調用std::remove和std::erase或者采用更復雜的邏輯。
注意事項
這種方法主要針對
std::vector類型的數(shù)組，如果是普通數(shù)組需要先轉換為std::vector。std::remove的使用可能會比較復雜，尤其是對于多種元素去重或者完全去重的情況。
十、自定義哈希函數(shù)去重（針對自定義類型數(shù)組）
原理
當數(shù)組中的元素是自定義類型時，可以定義一個哈希函數(shù)來計算元素的哈希值。然后可以使用類似于std::unordered_set的原理，創(chuàng)建一個基于自定義哈希函數(shù)的容器或者數(shù)據(jù)結構，通過比較哈希值來判斷元素是否重復。
示例代碼（假設自定義類型為MyType）:
#include <iostream>
#include <unordered_set>
struct MyType {
int a;
int b;
// 假設根據(jù)a和b計算哈希值
size_t operator()(const MyType& obj) const {
return std::hash<int>()(obj.a)^ std::hash<int>()(obj.b);
}
};
int main() {
MyType arr[] = { {1, 2}, {3, 4}, {1, 2}, {5, 6} };
int n = sizeof(arr)/sizeof(arr[0]);
std::unordered_set<MyType, MyType> s;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
}
for (auto it = s.begin(); it!= s.end(); it++) {
std::cout << "(" << it->a << ", " << it->b << ") ";
}
return 0;
}這里定義了MyType結構體，并為其定義了一個哈希函數(shù)。然后使用std::unordered_set結合自定義哈希函數(shù)對MyType類型的數(shù)組進行去重。
到此這篇關于C++數(shù)組去重十種方法的文章就介紹到這了,更多相關C++數(shù)組去重內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了使用C語言實現(xiàn)三子棋小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
算法無處不在，算法是程序的靈魂，而數(shù)據(jù)結構則是程序的骨架，二者共同構成了程序，那么如何評估算法的性能呢？理論上可以通過計算時間復雜度的方法來評估，但這是理性的認識，我們還有一種直觀的評估方法，那就是程序執(zhí)行的時間2022-08-08
C++實現(xiàn)圖片jpg格式變成16位565bmp格式
這篇文章主要為大家詳細介紹了C++如何實現(xiàn)圖片jpg格式變成16位565bmp格式,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下2025-03-03
這篇文章主要介紹了C語言預編譯#define(預處理),#define 機制包括了一個機制，允許把參數(shù)替換到文本中，這種實現(xiàn)通常稱為宏或者宏定義,下文更多的相關資料介紹需要的小伙伴可以參考一下2022-04-04
判斷一個數(shù)是不是素數(shù)的方法,需要的朋友可以參考一下2013-03-03
本文將對C++11的以上新特性進行簡單的講解，以便大家能夠快速了解到C++11對C++的易用性方面祈禱的巨大作用。2016-07-07
容器就是一些特定類型對象的集合,容器可以分為順序容器和關聯(lián)容器,下面這篇文章主要給大家介紹了關于C++常見容器的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了VC++進度條process Bar的用法,是進行VC++應用程序開發(fā)中非常常見的實用技巧,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C++ new-handler機制的相關資料，幫助大家更好的理解和使用c++，感興趣的朋友可以了解下2020-11-11![淺析C語言中對于char*和char[]的理解](http://img.jbzj.com/images/xgimg/bcimg9.png)
char * s 只是一個保存字符串首地址的指針變量，char a[]是許多連續(xù)的內(nèi)存單元，單元中的元素是char型，char * 和 char a[]具有相同的效果，源于字符串的本質，這篇文章主要介紹了C語言中對于char*和char[]的理解,需要的朋友可以參考下2023-02-02