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;
}
输出:
1 2 3 4 5
时间复杂度:O(n)
辅助空间:O(1)