c++++中利用指針進(jìn)行數(shù)組去重的核心在于通過雙指針實(shí)現(xiàn)原地修改和高效遍歷。1. 使用 slow 和 fast 兩個(gè)指針，slow 指向去重后的末尾，fast 遍歷數(shù)組；2. 當(dāng) fast 指向的元素與 slow 不同時(shí)，將其復(fù)制到 slow+1 的位置并移動(dòng) slow；3. 對(duì)于未排序數(shù)組，可先排序再用雙指針，或使用哈希表記錄已出現(xiàn)元素以實(shí)現(xiàn) o(n) 時(shí)間復(fù)雜度；4. 可借助 std::unique 和 std::erase 實(shí)現(xiàn)簡(jiǎn)潔但效率較低的去重方法；5. 對(duì)象或結(jié)構(gòu)體數(shù)組需重載 == 運(yùn)算符或提供自定義比較函數(shù)；6. 原地操作雖節(jié)省內(nèi)存但會(huì)修改原始數(shù)組，必要時(shí)應(yīng)創(chuàng)建副本或采用替代方案如哈希表、外部排序。
C++中利用指針進(jìn)行數(shù)組去重的核心在于，通過指針操作實(shí)現(xiàn)高效的遍歷和原地修改，避免額外的內(nèi)存開銷。雙指針?biāo)惴ㄊ顷P(guān)鍵，一個(gè)指針用于遍歷數(shù)組，另一個(gè)指針指向去重后的數(shù)組的末尾。
解決方案
核心思路是使用兩個(gè)指針：
slow
fast
fast
slow
fast
slow
fast
slow + 1
slow
立即學(xué)習(xí)“C++免費(fèi)學(xué)習(xí)筆記（深入）”；
以下是一個(gè)示例代碼：
#include <iostream>
#include <algorithm>
int* removeDuplicates(int* arr, int size) {
if (size == 0) {
return arr; // 空數(shù)組，無需去重
}
int* slow = arr;
int* fast = arr + 1;
while (fast < arr + size) {
if (*fast != *slow) {
*(++slow) = *fast; // 先移動(dòng) slow 指針，再賦值
}
++fast;
}
return arr; // 返回原始數(shù)組的指針，但數(shù)組已被修改
}
int main() {
int arr[] = {1, 1, 2, 2, 3, 4, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
removeDuplicates(arr, size);
// 輸出去重后的數(shù)組（實(shí)際長(zhǎng)度需要單獨(dú)計(jì)算）
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
// 計(jì)算去重后的數(shù)組的實(shí)際長(zhǎng)度
int* last = arr;
while(*(last+1) != 5 && last < arr + size - 1){
last++;
}
std::cout << "去重后的數(shù)組長(zhǎng)度: " << last - arr + 1 << std::endl;
return 0;
}這段代碼直接修改了原始數(shù)組。注意，雖然數(shù)組的內(nèi)容被修改了，但數(shù)組的大小并沒有改變。你需要單獨(dú)記錄去重后數(shù)組的實(shí)際長(zhǎng)度，例如通過計(jì)算
slow
如果數(shù)組未排序，一種方法是先對(duì)其進(jìn)行排序，然后再使用雙指針?biāo)惴āＥ判蚩梢允褂?
std::sort
std::unordered_set
#include <iostream>
#include <algorithm>
#include <unordered_set>
int removeDuplicatesUnsorted(int* arr, int size) {
if (size == 0) {
return 0;
}
std::unordered_set<int> seen;
int j = 0;
for (int i = 0; i < size; ++i) {
if (seen.find(arr[i]) == seen.end()) {
seen.insert(arr[i]);
arr[j++] = arr[i];
}
}
return j; // 返回去重后的數(shù)組長(zhǎng)度
}
int main() {
int arr[] = {5, 2, 1, 2, 3, 4, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int newSize = removeDuplicatesUnsorted(arr, size);
// 輸出去重后的數(shù)組
for (int i = 0; i < newSize; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
std::cout << "去重后的數(shù)組長(zhǎng)度: " << newSize << std::endl;
return 0;
}std::unique
std::erase
C++ 標(biāo)準(zhǔn)庫(kù)提供了
std::unique
std::erase
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> arr = {1, 1, 2, 2, 3, 4, 4, 5};
// 使用 std::unique 將重復(fù)元素移動(dòng)到末尾
auto it = std::unique(arr.begin(), arr.end());
// 使用 std::erase 刪除重復(fù)元素
arr.erase(it, arr.end());
// 輸出去重后的數(shù)組
for (int i = 0; i < arr.size(); ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
std::cout << "去重后的數(shù)組長(zhǎng)度: " << arr.size() << std::endl;
return 0;
}std::unique
std::vector
std::vector
如果數(shù)組包含的是對(duì)象或結(jié)構(gòu)體，你需要定義一個(gè)比較函數(shù)，用于判斷兩個(gè)對(duì)象是否相等。然后，可以將這個(gè)比較函數(shù)傳遞給
std::unique
==
例如：
#include <iostream>
#include <algorithm>
#include <vector>
struct Point {
int x;
int y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
int main() {
std::vector<Point> arr = {{1, 2}, {1, 2}, {3, 4}, {5, 6}, {5, 6}};
auto it = std::unique(arr.begin(), arr.end());
arr.erase(it, arr.end());
for (const auto& p : arr) {
std::cout << "(" << p.x << ", " << p.y << ") ";
}
std::cout << std::endl;
std::cout << "去重后的數(shù)組長(zhǎng)度: " << arr.size() << std::endl;
return 0;
}如果對(duì)象或結(jié)構(gòu)體沒有重載
==
std::unique
#include <iostream>
#include <algorithm>
#include <vector>
struct Point {
int x;
int y;
};
bool comparePoints(const Point& a, const Point& b) {
return a.x == b.x && a.y == b.y;
}
int main() {
std::vector<Point> arr = {{1, 2}, {1, 2}, {3, 4}, {5, 6}, {5, 6}};
auto it = std::unique(arr.begin(), arr.end(), comparePoints);
arr.erase(it, arr.end());
for (const auto& p : arr) {
std::cout << "(" << p.x << ", " << p.y << ") ";
}
std::cout << std::endl;
std::cout << "去重后的數(shù)組長(zhǎng)度: " << arr.size() << std::endl;
return 0;
}原地操作雖然節(jié)省了內(nèi)存，但它直接修改了原始數(shù)組，這在某些情況下可能不合適。如果需要保留原始數(shù)組，可以先創(chuàng)建一個(gè)副本，然后在副本上進(jìn)行去重操作。此外，如果數(shù)組非常大，原地操作可能會(huì)導(dǎo)致性能問題，因?yàn)樾枰l繁地移動(dòng)元素。在這種情況下，可以考慮使用其他算法，例如哈希表，或者使用外部排序。
以上就是C++中如何用指針實(shí)現(xiàn)數(shù)組去重 雙指針?biāo)惴ㄅc原地操作技巧的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注php中文網(wǎng)其它相關(guān)文章！
每個(gè)人都需要一臺(tái)速度更快、更穩(wěn)定的 PC。隨著時(shí)間的推移，垃圾文件、舊注冊(cè)表數(shù)據(jù)和不必要的后臺(tái)進(jìn)程會(huì)占用資源并降低性能。幸運(yùn)的是，許多工具可以讓 Windows 保持平穩(wěn)運(yùn)行。
微信掃碼
關(guān)注PHP中文網(wǎng)服務(wù)號(hào)
技術(shù)交流群
QQ掃碼
加入技術(shù)交流群
Copyright 2014-2025 http://ipnx.cn/ All Rights Reserved | php.cn | 湘ICP備2023035733號(hào)
444
收藏
