11202：统计不同值

题目

使用 qsort 实现 count_distinct_i64，统计 int64_t 数组中不同整数的数量。函数可以重排数组。

解析

先把相等元素排到相邻位置。非空数组至少包含一个不同值；随后每遇到一个与前项不同的元素，就把计数增加 1。

比较函数不能写成：

return *(const int64_t *)left - *(const int64_t *)right;

返回类型只有 int，而且两个 int64_t 值相减本身也可能发生有符号溢出。分别比较大小即可得到 -1、0 或 1。

解析

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

static int compare_i64(const void *left, const void *right) {
    int64_t a = *(const int64_t *)left;
    int64_t b = *(const int64_t *)right;
    return (a > b) - (a < b);
}

size_t count_distinct_i64(int64_t *items, size_t count) {
    if (count == 0) {
        return 0;
    }

    qsort(items, count, sizeof *items, compare_i64);

    size_t distinct = 1;
    for (size_t i = 1; i < count; ++i) {
        if (items[i] != items[i - 1]) {
            ++distinct;
        }
    }
    return distinct;
}

来源与改编

题型改编自 CSES Problem Set 的 Distinct Numbers，采用 CC BY-NC-SA 4.0。本题改为 C 标准库函数练习，并增加了比较器约束，完整说明见习题来源与许可。