在C++中，數(shù)組去重是一個常見的操作，以下是一些常見的數(shù)組去重方法：

一、使用std::sort和std::unique（STL方法）

原理

• 首先，std::sort函數(shù)用于對數(shù)組進行排序。它基于比較操作將數(shù)組元素按特定順序（默認(rèn)是升序）排列。例如，對于一個整數(shù)數(shù)組int arr[] = {5, 3, 4, 3, 2, 5};，std::sort會將其重新排列為有序的序列，如{2, 3, 3, 4, 5, 5}。

• 然后，std::unique函數(shù)用于去除相鄰的重復(fù)元素。它通過將不重復(fù)的元素移動到數(shù)組的前面部分來實現(xiàn)去重。在上面排序后的數(shù)組中，std::unique會將不重復(fù)的元素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只能去除相鄰的重復(fù)元素，所以在使用之前通常需要先對數(shù)組進行排序。

• 它不會改變數(shù)組的大小，只是將重復(fù)的元素移到數(shù)組的末尾部分，返回的是去重后有效元素的末尾位置。

二、使用std::set容器

原理

std::set是C++ STL中的關(guān)聯(lián)容器，它的特性是元素唯一。當(dāng)向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中的元素是按照特定順序存儲的（默認(rèn)是升序），如果不需要這種順序，可以考慮使用std::unordered_set，它在插入和查找操作上可能會更高效。

• 使用std::set去重會改變元素的存儲結(jié)構(gòu)，并且如果需要將去重后的結(jié)果再轉(zhuǎn)換回數(shù)組，需要額外的操作。

三、手動比較法（雙循環(huán)法）

原理

這種方法使用兩層循環(huán)。外層循環(huán)遍歷數(shù)組的每個元素，內(nèi)層循環(huán)用于比較當(dāng)前元素與之前已經(jīng)處理過的元素是否相同。如果找到相同的元素，則說明當(dāng)前元素是重復(fù)的，可以跳過或者進行相應(yī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ù)組部分。

注意事項

• 這種方法的時間復(fù)雜度較高，為O(n^2)O(n2)，其中n是數(shù)組的大小。當(dāng)數(shù)組規(guī)模較大時，性能可能會比較差。

• 它不需要額外的容器，但代碼相對復(fù)雜一些。

四、利用std::map記錄元素出現(xiàn)次數(shù)

原理

std::map是C++ STL中的關(guān)聯(lián)容器，它以鍵 - 值對的形式存儲數(shù)據(jù)。在這里，可以將數(shù)組元素作為鍵，元素出現(xiàn)的次數(shù)作為值。在遍歷數(shù)組時，如果元素第一次出現(xiàn)，則將其插入std::map中，值設(shè)為1；如果元素已經(jīng)存在，則將對應(yī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ù)信息，會占用一定的額外空間。

• 相比于直接比較的方法，雖然時間復(fù)雜度在平均情況下可能較好，但對于一些特殊情況可能會有一定的性能開銷。

五、使用std::unordered_set（哈希表去重）

原理

std::unordered_set是基于哈希表實現(xiàn)的關(guān)聯(lián)容器。它的插入和查找操作平均時間復(fù)雜度接近常數(shù)時間O(1)O(1)。當(dāng)向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ù)可能會導(dǎo)致哈希沖突，在極端情況下可能會影響性能。不過在大多數(shù)情況下，它的性能表現(xiàn)較好。

• 同樣，將去重后的結(jié)果轉(zhuǎn)換回數(shù)組可能需要額外的操作。

六、標(biāo)記法

原理

可以創(chuàng)建一個額外的布爾類型數(shù)組來標(biāo)記已經(jīng)出現(xiàn)過的元素。遍歷原始數(shù)組時，對于每個元素，檢查其在標(biāo)記數(shù)組中的對應(yīng)位置是否已經(jīng)被標(biāo)記。如果沒有被標(biāo)記，則說明該元素是第一次出現(xiàn)，將其加入去重后的結(jié)果中，并在標(biāo)記數(shù)組中標(biāo)記該元素；如果已經(jīng)被標(biāo)記，則說明是重復(fù)元素，跳過。

示例代碼：

#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; 
}

這里首先初始化標(biāo)記數(shù)組，然后在遍歷原始數(shù)組時，根據(jù)標(biāo)記數(shù)組判斷元素是否重復(fù)，并更新標(biāo)記數(shù)組和去重后的數(shù)組。

注意事項

• 這種方法需要額外創(chuàng)建一個與原始數(shù)組大小相同的布爾類型數(shù)組來進行標(biāo)記，會占用一定的額外空間。

• 它的時間復(fù)雜度取決于原始數(shù)組中重復(fù)元素的分布情況，但在最壞情況下也是O(n^2)O(n2)。

七、排序后單循環(huán)比較（優(yōu)化雙循環(huán)法）

原理

先對數(shù)組進行排序，這樣相同的元素就會相鄰。然后只需要一次循環(huán)遍歷數(shù)組，比較當(dāng)前元素和下一個元素是否相同。如果不同，則說明當(dāng)前元素是不重復(fù)的，可以進行相應(yīng)處理；如果相同，則說明是重復(fù)元素，可以跳過。

示例代碼:

#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ù)，時間復(fù)雜度為O(nlogn + n)O(nlogn+n)，其中nlognnlogn是排序的時間復(fù)雜度，n是遍歷數(shù)組的時間復(fù)雜度。

• 不過它需要先對數(shù)組進行排序，如果不需要排序后的結(jié)果，這可能會是一個額外的開銷。

八、利用數(shù)組指針和動態(tài)內(nèi)存分配

原理

可以創(chuàng)建一個動態(tài)分配內(nèi)存的新數(shù)組，然后通過指針遍歷原始數(shù)組。對于原始數(shù)組中的每個元素，檢查它是否已經(jīng)存在于新數(shù)組中。如果不存在，則將其添加到新數(shù)組中。這種方法可以避免使用一些復(fù)雜的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)比較將不重復(fù)的元素放入新數(shù)組，最后輸出并釋放內(nèi)存。

注意事項

• 這種方法需要手動管理動態(tài)分配的內(nèi)存，如果忘記釋放內(nèi)存會導(dǎo)致內(nèi)存泄漏。

• 雙循環(huán)比較導(dǎo)致時間復(fù)雜度為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刪除這些元素。需要注意的是，如果要去重所有元素，可能需要多次調(diào)用std::remove和std::erase或者采用更復(fù)雜的邏輯。

注意事項

• 這種方法主要針對std::vector類型的數(shù)組，如果是普通數(shù)組需要先轉(zhuǎn)換為std::vector。

• std::remove的使用可能會比較復(fù)雜，尤其是對于多種元素去重或者完全去重的情況。

十、自定義哈希函數(shù)去重（針對自定義類型數(shù)組）

原理

當(dāng)數(shù)組中的元素是自定義類型時，可以定義一個哈希函數(shù)來計算元素的哈希值。然后可以使用類似于std::unordered_set的原理，創(chuàng)建一個基于自定義哈希函數(shù)的容器或者數(shù)據(jù)結(jié)構(gòu)，通過比較哈希值來判斷元素是否重復(fù)。

示例代碼（假設(shè)自定義類型為MyType）:

#include <iostream>
#include <unordered_set>
struct MyType {
    int a; 
    int b; 
    // 假設(shè)根據(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結(jié)構(gòu)體，并為其定義了一個哈希函數(shù)。然后使用std::unordered_set結(jié)合自定義哈希函數(shù)對MyType類型的數(shù)組進行去重。

到此這篇關(guān)于C++數(shù)組去重十種方法的文章就介紹到這了,更多相關(guān)C++數(shù)組去重內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論