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

2024年8月28日 | 阅读 4 分钟

我们将得到一个已排序的数组作为输入。我们的任务是从集合中删除重复的元素，并将函数返回到主空间，在那里我们可以开始打印不含重复项的新排序数组。

我们可以用两种方法来解决这个问题，一种是使用额外的空间，另一种是使用常数级的额外空间，下面将通过代码和输出来讨论这两种方法。

C++ 代码：使用额外空间

// Here in the below notes, we are writing down the C++ programming language 
// code to demonstrate the concept of a Simple C++ program to
// Remove duplicates from the sorted array with code and example, and their 
// respective output.
#include <iostream>
using namespace std;


// the below function which we have written will help us with removing the 
// duplicate elements in the array which are passed into it as an argument
// it will return us the size of the new modified array once finishing 
// the operation of removing the duplicate elements
int removeDuplicates(int arr[], int n)
{
	
	
	// this is a small (if) check condition where we will be checking if 
	// whether the element which is passed as an argument contains one element
	// or no elements and return the n value if the condition is true.
	if (n == 0 || n == 1)
		return n;

	int temp[n];


	// from j equals to 0 onwards; we start traversing the elements in the
	// array passed as an argument
	
	// we have an uninitialised variable j to 0, which can then start 
	// traversing from 0 to the ray's size w, n-1.
	
	int j = 0;
	
	// this simple for loop has a  simple check condition where we check if 
	// the present element where we are trying to store is equal to the next 
	// element or not
	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 been used previously
	// whether the last part of the array is individual, a repeated one
   // we are trying to keep here what was not, therefore in the code
	temp[j++] = arr[n - 1];

	// we are trying to store the array in the temporary array created 
	// after modifying the original array using a simple for loop
	for (int i = 0; i < j; i++)
		arr[i] = temp[i];

	return j;
}

// the main driver code functionality starts from here
int main()
{
	int arr[] = { 21, 22, 22, 23, 24, 24, 24, 25, 25 };
	int n = sizeof(arr) / sizeof(arr[0]);


	// the C++ programming language has in-built removeDuplicates()
	// function, which helps us with not writing huge lines of code instead 
	// do the task in lightning less time complexity.
   // after operating, it returns to us the size of the new array
	n = removeDuplicates(arr, n);

	
	// the below small for-loop code snippet helps us with printing down the
	// updated array after removing the duplicate elements to the display
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";

	return 0;
}

输出

31 32 33 34 35

1. 常数级额外空间

C++ code
// Here in the below notes, we are writing down the C++ programming language
// code to demonstrate the concept of a Simple C++ program to
// Remove duplicates from the sorted array with code and example, and their 
// respective output.
#include<iostream>
using namespace std;

// the remove duplicates in-built function helps us not to write 
// the same extra lines of code
int removeDuplicates(int arr[], int n)
{
	if (n==0 || n==1)
		return n;

	// from j equals to 0 onwards; we start traversing the elements in the
	// array passed as an argument

	int j = 0;


	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;
}

// the main driver code functionality starts from here
int main()
{
	int arr[] = {31, 32, 32, 33, 34, 34, 34, 35, 35};
	int n = sizeof(arr) / sizeof(arr[0]);

	
	n = removeDuplicates(arr, n);


	// the below small for-loop code snippet helps us with printing down the
	// updated array after removing the duplicate elements from the display

	for (int i=0; i<n; i++)
		cout << arr[i] << " ";

	return 0;
}

输出

31 32 33 34 35

下一主题在 C++ 中使用元组和对从函数返回多个值

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

1. 常数级额外空间

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

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

1. 常数级额外空间

相关帖子

C++ Valloc() 函数

二叉树有多少个子节点

C++ 程序实现 Coppersmith Freivald 算法

C++ 中 array::fill() 和 array::swap() 的区别

C++ std::stol 函数

C++ 学生数据管理

C++ 程序实现 Bitap 字符串匹配算法

C++ 中最快的排序算法

C++ 显示数字因数的程序

通过将两个连续的 1 转换为 0 来确定游戏获胜者（C++）

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器