c - 查找 int 链表中最常出现的元素的最简单方法

Question

我有一个 C 整数链接列表，我正在尝试找到一种有效的方法来查找列表中最常见的元素。

到目前为止，我已经考虑过创建一个存储计数器的新节点结构，但如果有更简单的方法，我想避免这种情况。

有没有更直接的方法来做到这一点？

Answer 1

这里有四种解决方案:

1. 如果您有良好的哈希表实现，则可以通过将计数与哈希表中的每个值一起存储来实现线性时间，如果该值已在表中，则增加计数。对哈希表的最后一次扫描将找到计数最大的元素。这具有线性时间和空间复杂度。该解决方案将用于具有内置 HashMap 的语言，但 C 在标准库中没有提供任何 HashMap ，因此您必须实现它，这是一项艰巨的任务。

2. 您可以对列表的副本进行排序:

• 如果无法修改列表，请复制该列表(线性时间和空间复杂度)。
• 使用链接列表的归并排序对列表进行排序(时间复杂度O(n.log(n)))。
• 扫描列表，计算当前元素出现的次数，跟踪该值并计算最大计数(线性时间)。
• 释放副本(线性时间)。
• 完成。

更简单，但时间是二次方且没有空间开销:当您在列表中迭代时，计算当前节点中值在列表其余部分中出现的次数，跟踪该值并计算最大的值计数:

int most_common_value(const node *p) {
    int best_count = 0, best_value = 0;
    for (; p; p = p->next) {
        int count = 1;
        for (const node *q = p->next; q; q = q->next) {
            count += (q->value == p->value);
        }
        if (best_count < count) {
            best_count = count;
            best_value = value;
        }
    }
    return best_value;
}

如果数据是取值范围比较小的整数，可以使用计数数组，实现时间和空间的线性:

int most_common_value(const node *p) {
    if (!p)
        return 0;

    int best_count = 0, best_value = 0;
    int min = p->value, max = p->value, length = 1;

    for (const node *q = p->next; q; q = q->next) {
        if (min > q->value)
            min = q->value;
        if (max < q->value)
            max = q->value;
        length++;
    }
    int range = max / 2 - min / 2;
    if (range <= 1000 && range / length > length) {
        int count[max - min + 1];
        for (int i = 0; i <= max - min; i++) {
            count[i] = 0;
        }
        for (const node *q = p; q; q = q->next) {
            count[q->value - min]++;
        }
        for (int i = 0; i <= max - min; i++) {
            if (best_count < count[i]) {
                best_count = count[i];
                best_value = min + i;
            }
        }
    } else {
        /* use some other method */
        for (; p; p = p->next) {
            int count = 1;
            for (const node *q = p->next; q; q = q->next) {
                count += (q->value == p->value);
            }
            if (best_count < count) {
                best_count = count;
                best_value = value;
            }
        }
    }
    return best_value;
}