c++ 升序数组去重

在C++中，对升序数组去重，一种常见的方法是利用双指针技巧。以下是简单的步骤：

1. 定义两个指针，`i` 和 `j`，初始值都为0，分别表示已处理的元素和未处理的区域的起始位置。
2. 当`i < j`时，继续循环：
a. 如果`arr[i]`等于`arr[j]`，说明找到了重复项，移动右边界 `j++`。
b. 否则，将`arr[i++]`复制到新位置，然后`i++`，即保留当前元素并移到下一个位置。
3. 循环结束后，`arr[0...j)` 就是一个去重后的升序数组。

这种方法的时间复杂度通常是O(n)，其中n是数组长度，因为它只遍历一次数组。空间复杂度是O(1)（除原数组外），因为我们只用到了常数级别的额外存储空间。

#include <iostream>
using namespace std;

void removeDuplicates(int arr[], int n) {
    if (n == 0 || n == 1)
        return;
    
    int i = 0, j = 1; // 初始化两个指针
    while (j < n) {
        if (arr[i] != arr[j]) {
            i++; // 移动已排序部分的指针
            arr[i] = arr[j]; // 复制元素到已排序部分
        }
        j++;
    }
    arr[i+1] = 0; // 去掉多余的0，保证数组长度与实际元素一致
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    removeDuplicates(arr, n);
    for (int i = 0; i <= n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}