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

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: (使用额外空间)

  1. 创建一个辅助数组temp []来存储唯一元素。
  2. 遍历输入数组,并一次将arr []的唯一元素复制到temp []。 同时跟踪唯一元素的计数。 让这个计数是 j
  3. 从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;
}  

输出:

1 2 3 4 5

时间复杂度:O(n)

辅助空间:O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例