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

Question

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

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

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

Answer 1

这里有四个解决方案：

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

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

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

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

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

4. 如果数据是一个值范围相对较小的整数，则可以使用计数数组并实现线性时间和空间：

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