c - 计算无序数组中唯一元素的程序

Question

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

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

Answer 1

有时简单就是规则。

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

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

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

最坏情况下的执行时间是所有值都是唯一的(即数组中没有重复值)。