0

我正在处理一个问题，它要求您在按字典顺序排序的排列中找到字符串的排名。

O(N^2) 很清楚。

一些网站也有O(n) 解决方案。优化的部分基本上是预先填充一个count array这样的

count[i] 包含 str 中存在且小于 i 的字符数。

我知道这会降低复杂性，但我无法理解我们如何计算这个数组。这是执行此操作的函数（取自链接）：

// Construct a count array where value at every index
// contains count of smaller characters in whole string
void populateAndIncreaseCount (int* count, char* str)
{
    int i;

    for( i = 0; str[i]; ++i )
        ++count[ str[i] ];

    for( i = 1; i < 256; ++i )
        count[i] += count[i-1];
}

有人可以提供这个功能的直观解释吗？

4

2 回答 2

0

该解决方案是进行桶排序，然后对输出进行排序。

桶排序是O(items + number_of_possible_distinct_inputs)对于固定字母表可以宣传为O(n).

然而在实践中，UTF 会产生一个相当大的字母表。因此，我建议使用快速排序。因为快速排序分为 , 的三个桶，对大字符集<有效>，=但仍然利用小字符集。

于 2018-04-28T16:46:53.277 回答
0

又经历了一遍才明白。由于 c++ 中的语法错误而感到困惑。它实际上是在做一件非常简单的事情（这是 java 版本：

void populateAndIncreaseCount(int[] count, String str) {
    // count is initialized to zero for all indices
    for (int i = 0; i < str.length(); ++i) {
      count[str.charAt(i)]++;
    }

    for (int i = 1; i < 256; ++i)
      count[i] += count[i - 1];
  }

在第一步之后，其字符存在于字符串中的索引非零。然后，对于 count 数组中的每个索引，它将是所有计数的总和，index-1因为数组表示按字典顺序排序的字符。而且，在每次搜索之后，我们还更新了 count 数组：

// 从 count[] 数组中删除一个字符 ch // 由 populateAndIncreaseCount() 构造

void updatecount (int* count, char ch)
{
    int i;
    for( i = ch; i < MAX_CHAR; ++i )
        --count[i];
}
于 2018-04-28T17:43:26.923 回答