如何从数组中有效地提取唯一值？

I would like to extract unique values from my (dynamically allocated) array. I have something like this :

我想从我的(动态分配的)数组中提取唯一值。我有这样的事情:

    [0]     0   int
    [1]     1   int
    [2]     2   int
    [3]     2   int
    [4]     2   int
    [5]     5   int
    [6]     6   int
    [7]     6   int
    [8]     8   int
    [9]     9   int
    [10]    10  int
    [11]    8   int
    [12]    12  int
    [13]    10  int
    [14]    14  int
    [15]    6   int
    [16]    2   int
    [17]    17  int
    [18]    10  int
    [19]    5   int
    [20]    5   int

I would like to have array of size 12 with every record in it being unique value form the other array.

我希望有大小为12的数组,其中每个记录都是另一个数组的唯一值。

How can I do that ?

我怎样才能做到这一点 ?

EDIT I forgot to mention that I cannot use STL containers (like std::vector or std::list)

编辑我忘了提到我不能使用STL容器(如std :: vector或std :: list)

6 个解决方案

#1

First you need to sort the array, then iterate over the sorted array and check if the previous or next entry are the same as the current entry. If not then the value is unique.

首先,您需要对数组进行排序,然后遍历排序的数组并检查上一个或下一个条目是否与当前条目相同。如果不是,那么该值是唯一的。

Edit: I might have misunderstood the question... One way to get what you want is to iterate over the array. For each value check the value already exists in the other array, if not the copy it there. This might have to be done in two steps, once to get the number of unique entries (using an array of the same size as the existing) and one to get an array of correct size.

编辑:我可能误解了这个问题......获得你想要的东西的一种方法是迭代数组。对于每个值检查,该值已存在于另一个数组中,如果不存在则复制它。这可能必须分两步完成,一次是获取唯一条目的数量(使用与现有大小相同的数组),另一步是获取正确大小的数组。

#2

Use std::unique after sorting your array with your favorite sorting algorithm (e.g. std::sort)

使用您喜欢的排序算法(例如std :: sort)对数组进行排序后,使用std :: unique

Edit: Without STL, the simplest solution would be to find the min & max values in the array and dynamically allocate an array of bool. Traverse the array and if you see the element, set the corresponding bool element to true. Allocate a new int array with the total number of unique elements and fill it up with the data from the bool array.

编辑:没有STL,最简单的解决方案是找到数组中的最小值和最大值,并动态分配一个bool数组。遍历数组,如果看到元素,则将相应的bool元素设置为true。使用唯一元素的总数分配一个新的int数组,并用bool数组中的数据填充它。

Recommended: Sort the array and remove consecutive elements. Implementing quick sort isn't too hard, and if you're dealing with integers, radix sort might be better.

推荐:对数组进行排序并删除连续元素。实现快速排序并不太难,如果你处理整数,基数排序可能会更好。

#3

You can use a std::set. Add all the elements to it, at the end only unique values will be present.

您可以使用std :: set。将所有元素添加到其中,最后只会出现唯一值。

#4

#include <iostream>
#include <stdlib.h>
using namespace std;

int cmpfun(const void * a, const void * b){
  return (*(int*)a - *(int*)b);
}
int main(){
  int n,i,j=0;
  cout<<"Enter the number of elements in the array:\n";
  cin>>n;
  int arr[n],arr_new[n];
  for(i=0;i<n;i++)
       cin>>arr[i];
  qsort(arr, n, sizeof(int), cmpfun); /*Sorting the array; if you aren't allowed to use any library sorting method,
                                   then I suggest to implement one sorting function on your own.*/

  for(i=0;i<n;i++){
       arr_new[j++]=arr[i];
        // Excluding all duplicates
       while(i<(n-1) && arr[i]==arr[i+1])
                 i++;
  }
  for(i=0;i<j;i++)
  cout<<arr_new[i]<<" ";

return 0;}

The main aim is to make sure duplicates are ignored. So, you should first sort the array and then in O(n) time, traverse the array, ignoring all repetitions. While traversing the array, copy all the unique values(values which you encounter for the first time) to the new array.

主要目的是确保忽略重复项。因此,您应首先对数组进行排序,然后在O(n)时间内遍历数组,忽略所有重复。遍历数组时,将所有唯一值(第一次遇到的值)复制到新数组。

The only thing I find that can concern you is that the respective ordering of elements in the old array isn't preserved in the new array. But if you are only concerned with finding the unique values, then this method should work fine.

我发现唯一可能涉及到的问题是旧数组中元素的相应排序不会保留在新数组中。但是如果你只关心找到唯一值,那么这个方法应该可以正常工作。

#5

You can use an hash set (unordered_set) to store each value of the source array. The set will automatically store only unique values. Then, if you really need an array and not a set, you can create an array of the good size and fill it with the elements of the set.

您可以使用哈希集(unordered_set)来存储源数组的每个值。该集将自动仅存储唯一值。然后,如果你真的需要一个数组而不是一个集合,你可以创建一个大小合适的数组,并用集合的元素填充它。

#6

If you know the maximum and minimum you can create a new array with all the possible values you can get and then loop through your dynamic array . For each value set 1 for the new array by taking as the index of the value. As an example:- say you have data like this 1,2,2,4,6

如果您知道最大值和最小值,则可以创建一个包含所有可能值的新数组,然后循环遍历动态数组。对于新数组的每个值集1,取以值作为索引。举个例子: - 说你有这样的数据1,2,2,4,6

if the range is 1 to 7

如果范围是1到7

the second array will be like this

第二个数组将是这样的

1 2 3 4 5 6 7
1 1 0 1 0 1 0

The complexity of the algo will be 2n

算法的复杂性将是2n

#1