C++程序从排序数组中删除重复项

给定一个已排序的数组，任务是从数组中删除重复元素。

例子：

输入： arr[] = {2, 2, 2, 2, 2}
输出： arr[] = {2}
新长度 = 1

输入： arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}
输出： arr[] = {1, 2, 3, 4, 5}
新长度 = 5

方法1： (使用额外空间)

创建一个辅助数组temp []来存储唯一元素。
遍历输入数组，并一次将arr []的唯一元素复制到temp []。同时跟踪唯一元素的计数。让这个计数是 j 。
从temp []复制 j 个元素到arr []，并返回j

// 删除重复的Simple C ++程序
#include <iostream>
using namespace std;
  
// Function to remove duplicate 
// elements This function returns 
// new size of modified array.
int removeDuplicates(int arr[], int n)
{
    // Return, if array is empty or 
    // contains a single element
    if (n == 0 || n == 1)
        return n;
  
    int temp[n];
  
    // Start traversing elements
    int j = 0;
  
    // If current element is not equal 
    // to next element then store that 
    // current element
    for (int i = 0; i < n - 1; i++)
        if (arr[i] != arr[i + 1])
            temp[j++] = arr[i];
  
    // Store the last element as whether 
    // it is unique or repeated, it hasn't 
    // stored previously
    temp[j++] = arr[n - 1];
  
    // Modify original array
    for (int i = 0; i < j; i++)
        arr[i] = temp[i];
  
    return j;
}
  
// Driver code
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 
                 4, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // RemoveDuplicates() returns 
    // new size of array.
    n = removeDuplicates(arr, n);
  
    // Print updated array
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
  
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)```

输出：

1 2 3 4 5

时间复杂度： O(n)

辅助空间： O(n)

方法2： (常数额外空间)

只需在方法1中维护与不同数组所维护的相同数组的单独索引即可。

// 在原地删除重复的C ++程序
#include<iostream>
using namespace std;
  
// Function to remove duplicate 
// elements. This function returns 
// new size of modified array.
int removeDuplicates(int arr[], int n)
{
    if (n==0 || n==1)
        return n;
  
    // To store index of next 
    // unique element
    int j = 0;
  
    // Doing same as done in Method 1
    // Just maintaining another updated 
    // index i.e. j
    for (int i = 0; i < n - 1; i++)
        if (arr[i] != arr[i + 1])
            arr[j++] = arr[i];
  
    arr[j++] = arr[n - 1];
  
    return j;
}
  
// Driver code
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 
                 4, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // removeDuplicates() returns new 
    // size of array.
    n = removeDuplicates(arr, n);
  
    // Print updated array
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
  
    return 0;
}