数组中不同的唯一元素

Question

我尝试编写代码来计算给定数组中不同唯一元素的数量，但得到了不需要的输出。{ 2, 7, 5, 8, 9, 5, 7, 5, 5, 3}这是给定的数组元素。不同的唯一值{ 2, 8, 9, 3}意味着有 4 个。但我的程序返回 6: { 2, 5, 8, 9, 7, 3}

这是我的代码：

 #include <stdio.h>
 #include <stdlib.h>


int unique(int *arr, int n)
{
     int u = 1;

     for (int i = 1; i < n; ++i)
     {
        int is_u = 1;
        for (int j = 0; is_u && j < i; ++j)
        {
             if (arr[j] == arr[i]) is_u = 0;
        }
        if (is_u) ++u;
     }
     return u;
}


int main(void) {
    int arr[] = { 2, 7, 5, 8, 9, 5, 7, 5, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", unique(arr, n));
    return 0;
}

Answer 1

您需要检查整个数组（当前您的内部循环仅到达i）。

    for (int j = 0; is_u && j < n; ++j)
    {
         /* i != j to avoid comparing an element with itself. */
         if (i != j && arr[j] == arr[i]) is_u = 0;
    }

你的显然是一个 O(n*n) 算法。您可以对后续元素进行排序和检查，以在 O(n log n) 中执行相同操作。

如果您可以使用额外的 O(n) 内存来使用辅助数组作为“计数器”，那么它也可以在 O(n) 时间复杂度内完成。