C语言 一个计算无序数组中唯一元素的程序

A program that counts unique elements in an un-ordered array

提问by LearningCODE

int num_distinct(int a[], int n)
{
  int i, k, j, count=0;
  int max = a[0];

  for (i = 1; i < n; i++) {
    if (max < a[i]) {
      max = a[i];
    }
  }
  for (k = 0; k < n; ++k) {
    for (j = 0; j < n; ++j) {
      if (a[j] == max) {
        ++count;
        --max;
        break;
      }
    }
  }
  return (count);
}

What i tried to do is find the max in the array and compare that to the rest of the elements in the array. It works, but when the array skips a number i.e. (1,2,2,5,6,7,8) <-- it skipped 3 and 4. My code will only count 8,7,6,5 which returns 4 unique numbers.

我试图做的是找到数组中的最大值并将其与数组中的其余元素进行比较。它可以工作，但是当数组跳过一个数字时，即 (1,2,2,5,6,7,8) <-- 它跳过了 3 和 4。我的代码只会计算 8,7,6,5 返回 4独特的数字。

回答by Gravity

just to let you know, @kcDod's algorithm is flawed. It won't count elements like this: 1, 2, 3, 4, 9000, 4, 2 try and you will see:

只是让您知道，@kcDod 的算法有缺陷。它不会计算这样的元素： 1, 2, 3, 4, 9000, 4, 2 尝试，你会看到：

the below code will count regardless of the elements and requires much less power, you don't count unique elements by incrementing or decrementing the maximum in an array, I don't know where you got that idea.

无论元素如何，下面的代码都会计数，并且需要的功率要少得多，您不会通过增加或减少数组中的最大值来计算唯一元素，我不知道您从哪里得到这个想法。

int unique_elements(int arr[], int len) {

    int counted[len], j, n, count, flag;

    counted[0] = arr[0]; 

    count = 1;/*one element is counted*/

        for(j=0; j <= len-1; ++j) {
        flag = 1;;
        /*the counted array will always have 'count' elements*/
        for(n=0; n < count; ++n) {
            if(arr[j] == counted[n]) {
                flag = 0;
            }
        }
        if(flag == 1) {
            ++count;
            counted[count-1] = arr[j];
        }
    }
    return count;
}


int main(void) {
    int arr[13] = {1, 2, 2, 123121, 123121, 3, 5, 6 , 7, 7, 14, 2, 16};
    printf("%d", unique_elements(arr, 13));
    return 0;
}

回答by Rob

Sometimes simplicity rules.

有时简单规则。

int unique_elements(int arr, int len)
{
     if (len <= 0) return 0;
     int unique = 1;

     for (int outer = 1; outer < len; ++outer)
     {
        int is_unique = 1;
        for (int inner = 0; is_unique && inner < outer; ++inner)
        {  
             if (arr[inner] == arr[outer]) is_unique = 0;
        }
        if (is_unique) ++unique;
     }
     return unique;
}

The logic is that the outer loop picks the value to be tested, and the inner loop checks it against all preceding values. If the value is found, it is not unique, so the count is incremented.

逻辑是外循环选择要测试的值，内循环根据所有前面的值检查它。如果找到该值，则它不是唯一的，因此计数会增加。

The advantage of this is no usage of temporary storage (whether a VLA, or use of malloc()). It also does not try to work out the max, or count number of repetitions, or anything like that.

这样做的好处是不使用临时存储（无论是 VLA，还是使用 malloc()）。它也不会尝试计算最大重复次数或计算重复次数，或类似的东西。

The worst case execution time is if all values are unique (i.e. no repeated values in the array).

最坏的执行时间是所有值都是唯一的（即数组中没有重复的值）。

回答by Kavindu Dodanduwa

This shall work .. Replace second for loop set with this.

这将工作.. 用这个替换第二个 for 循环集。

int flag = 0; // We need to flag that we found a max in the iteration. So don't count again

for (k = 0; k < n;){
     for (j = 0; j < n; ++j) {         
          if (a[j] == max){
             if (flag==0){
                 ++count; // We count an occurrence only once 
                 flag = 1;
              }
             k++; // We should decrease the search when we found an element from original array
          }
      }
    // Reset parameters
    --max;
    flag = 0;
}

A working example :

一个工作示例：

#include <stdio.h>

int main()
{
    int a[7] = { 7,2,2,4,5,6,7};
    int n = 7; // Number of elements in the array 

    int max=0;
    int i, k, j=0;

    for (i = 1; i < n; i++)
    {
        if (max < a[i])
         {
            max = a[i];
        }
    }

    int count=0;
    int flag = 0;

    for (k = 0; k < n;)
    {
        for (j = 0; j < n; ++j)
        {
            if (a[j] == max)
            {
                if (flag==0)
                {
                    ++count;
                    flag = 1;
                }
             k++;
         }
        }
        --max;
         flag = 0;
    }

    printf("Unique elements : %d\n",count);
}

Output :

输出 ：

Unique elements : 5 

回答by KAKY

Your algorithm might take much longer time when the max value in the array is very big. Memorising which element was counted already seems to be better in order to reduce computational complexity.

当数组中的最大值非常大时，您的算法可能需要更长的时间。为了降低计算复杂度，记住已经计算了哪个元素似乎更好。

My code below memorises which element was counted and skips counting an element if it was counted already. I use a flag array to memorise counted element.

我下面的代码记住了哪个元素被计数，如果已经被计数，则跳过对元素的计数。我使用一个标志数组来记住计数元素。

#include <stdlib.h>

int num_distinct(int a[], int n) {
    int* flag;
    int all_counted = 0;
    int i, cur, count = 0;
    int cur_flag;

    flag = (int*)malloc(n);
    for (i = 0; i < n; i++) flag[i] = 0;

    while (all_counted == 0) {
        cur_flag = 0;
        for (i = count; i < n; i++) {
            if (cur_flag == 0 && flag[i] == 0) {
                flag[i] = 1;
                cur_flag = 1;
                cur = a[i];
                count++;
            } else if (cur_flag == 1 && cur == a[i]) {
                flag[i] = 1;
            }
        }
        if (cur_flag == 0) all_counted = 1;
    }
    free(flag);
    return count;
}