1

我几乎已经完成了这个问题的代码，我将说明如下：

鉴于：

长度为“n”的数组（例如 n = 10000）声明如下，

     char **records = malloc(10000*sizeof(*records));

每个 record[i] 都是一个 char 指针，指向一个非空字符串。

     records[i] = malloc(11);

字符串是固定长度的（10 个字符 + '\0'）。

要求：

返回上述数组中出现频率最高的字符串。

但是现在，我有兴趣获得一种比我目前拥有的原始算法稍微不那么残酷的算法，即在两个 for 循环中筛选整个数组:(，将两个循环遇到的字符串存储在一个类似的临时数组中大小（'n' - 如果都是唯一字符串）用于与下一个字符串进行比较。内部循环从'外部循环位置 + 1 '迭代到' n '。同时，我有一个类似的整数数组size - 'n', 用于计算重复出现次数，每个第 i个元素对应于比较数组中的第 i个（唯一）字符串。然后找到最大的整数并使用它在比较数组中的索引返回最常出现的字符串.

我希望我足够清楚。我自己对算法感到很羞耻，但必须这样做。我相信在 C 中有更聪明的方法可以做到这一点。

有一个伟大的星期天，

干杯!

4

2 回答 2

3

如果不擅长好的算法（谷歌、维基百科和 Stackoverflow 对我来说已经足够好了），我想到的一个解决方案是对数组进行排序，然后使用单个循环来遍历条目。只要当前字符串与前一个字符串相同，就为该字符串增加一个计数器。完成后，您将获得一个字符串及其出现的“列表”，然后可以根据需要对其进行排序。

于 2013-01-06T06:44:21.140 回答
2

在大多数语言中，通常的方法是构造一个哈希表，将字符串映射到计数。这具有 O(N) 复杂度。

例如，在 Python 中（尽管通常您会为此使用 collections.Counter，甚至可以使用更专业的 Python 知识使这段代码更简洁，但我已经明确说明以进行演示）。

def most_common(strings):
    counts = {}
    for s in strings:
        if s not in counts:
            counts[s] = 0
        counts[s] += 1
    return max(counts, key=counts.get)

但是在 C 中，标准库中没有哈希表（尽管在 C++ 中，您可以使用 STL 中的 hash_map），因此可以进行排序和扫描。这是 O(N.log(N)) 复杂度，比最优更差，但非常实用。

这是一些实现此功能的 C（实际上是 C99）代码。

int compare_strings(const void*s0, const void*s1) {
    return strcmp((const char*)s0, (const char*)s1);
}

const char *most_common(const char **records, size_t n) {
    qsort(records, n, sizeof(records[0]), compare_strings);
    const char *best = 0;  // The most common string found so far.
    size_t max = 0;  // The longest run found.
    size_t run = 0;  // The length of the current run.
    for (size_t i = 0; i < n; i++) {
        if (!compare_strings(records[i], records[i - run])) {
            run += 1;
        } else {
            run = 1;
        }
        if (run > max) {
            best = records[i];
            max = run;
        }
     }
     return best;
}
于 2013-01-06T08:05:44.787 回答