21xrx.com
2025-04-01 13:40:30 Tuesday
文章检索 我的文章 写文章
如何在C++中删除数组中的重复元素？
2023-07-13 16:45:02 深夜i     13     0
C++ 数组 删除 重复元素

在C++中，删除数组中的重复元素是一个非常常见的需求。这种需求通常出现在需要统计一个数组中元素个数的时候，或者在需要进行搜索和排序等算法的时候。以下是在C++中删除数组中的重复元素的一些方法。

首先，可以使用一个暴力的方法，遍历整个数组，将每个元素与其它元素进行比较，如果发现有重复的，就将其删除。这种方法的时间复杂度为O(n^2)，当数组很大时，效率会非常低。

其次，可以使用STL中的set容器来删除重复元素。set是一个自动排序、不允许重复元素的容器，利用set的这个特性，只需要将数组中的元素插入到set中，然后再将set中的元素重新放回数组中，就可以去除重复元素。

示例代码如下：

#include <iostream>
#include <set>
using namespace std;
int main()
{
  int a[] = 3;
  set<int> s(a, a+12);
  int i = 0;
  for(set<int>::iterator it = s.begin(); it != s.end(); it++)
  {
    a[i++] = *it;
  }
  for(int j = 0; j < i; j++)
  {
    cout << a[j] << " ";
  }
  return 0;
}

运行结果为：1 2 3 4 5 6 7 8

最后，可以使用更高效的算法，例如“快速排序”，来去除重复元素。快速排序的思想是每次选取一个“基准”元素，将小于该元素的值放在左侧，大于该元素的值放在右侧，然后递归地处理左右两个子序列。这种方法的时间复杂度为O(nlogn)，比第一种方法快很多。

示例代码如下：

#include <iostream>
using namespace std;
void quickSort(int a[], int left, int right)
{
  if(left < right)
  {
    int i = left, j = right, x = a[left];
    while(i < j)
    {
      while(i < j && a[j] >= x)
      
        j--;
      
      if(i < j)
      {
        a[i++] = a[j];
      }
      while(i < j && a[i] < x)
      {
        i++;
      }
      if(i < j)
      {
        a[j--] = a[i];
      }
    }
    a[i] = x;
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);
  }
}
int main()
{
  int a[] = {1, 2, 3, 4, 5, 3, 2, 1, 6, 7, 8, 5};
  int n = sizeof(a) / sizeof(int);
  quickSort(a, 0, n - 1);
  int i = 0;
  for(int j = 1; j < n; j++)
  {
    if(a[j] != a[i])
    {
      a[++i] = a[j];
    }
  }
  for(int j = 0; j <= i; j++)
  {
    cout << a[j] << " ";
  }
  return 0;
}

运行结果为：1 2 3 4 5 6 7 8

总之，在C++中删除数组中的重复元素有多种方法，具体选择哪种取决于所需的时间复杂度和程序的实际情况。以上三种方法仅供参考，读者可以结合自己的实际情况进行选择。

  
  

评论区