范围内出现最频繁的字符

Question

我有一个长度为n的字符串s。在范围i..j内查找最频繁的字符，你需要使用哪种最有效的数据结构/算法？

该字符串不会随时间变化，我只需要重复查询并询问s[i]，s[i + 1]，...，s[j]中最频繁的字符。

- Momonga

---

你所关心的字符串和区间的预期长度是多少？ - Ivaylo Strandjev

@Ivaylo 看起来那是一个变量。 - crush

n 的大小大约为 10^6，我也需要大约 10^6 个查询。 - Momonga

ASCII，其他单字节字符集还是Unicode？ - MSalters

Answer 1

一个数组，其中包含每个字符出现的次数。在遍历字符串时，您可以增加相应的值。在执行此操作的同时，您可以记住数组中的当前最大值；或者在最后查找数组中的最高值。

伪代码

arr = [0]
for ( char in string )
   arr[char]++
mostFrequent = highest(arr)

- Luchian Grigore

---

@IvayloStrandjev 添加一个答案 :) - Luchian Grigore

@IvayloStrandjev 我不明白这样做怎么更有效率 - 它基本上是完全相同的答案。 - Luchian Grigore

他正在创建一个多维数组。 - crush

@LuchianGrigore 我可能误解了你的回答，但在我看来，你的答案复杂度是O(NQ)，而我的复杂度是O(N + LQ)，其中L是字母表的大小，Q是查询数量。 - Ivaylo Strandjev

我认为这里的真正问题是OP没有定义“高效”。它需要在计算或存储方面高效吗？ - crush

+1 这是最省时间的方法，但排序和计数最高元素更省空间（请参见我的答案）。 - TemplateRex

Answer 2

如果您希望在区间上获得高效的结果，可以在序列的每个索引处构建一个积分分布向量。然后通过从j + 1和i处减去积分分布，可以获得从s [i]，s [i + 1]，...，s [j]的区间分布。

以下是Python中的一些伪代码。我假设您的字符是chars，因此有256个分布条目。

def buildIntegralDistributions(s):
    IDs=[]        # integral distribution
    D=[0]*256
    IDs.append(D[:])
    for x in s:
        D[ord(x)]+=1
        IDs.append(D[:])
    return IDs

def getIntervalDistribution(IDs, i,j):
    D=[0]*256        
    for k in range(256):
        D[k]=IDs[j][k]-IDs[i][k]
    return D

s='abababbbb'
IDs=buildIntegralDistributions(s)
Dij=getIntervalDistribution(IDs, 2,4)

>>> s[2:4]
'ab'
>>> Dij[ord('a')]  # how many 'a'-s in s[2:4]?
1
>>> Dij[ord('b')]  # how many 'b'-s in s[2:4]?
1

- ssegvic

---

我相信我已经在我的答案中解释了相同的想法。 - Ivaylo Strandjev

我考虑过这个，但是除非有一种快速减去分布的方法，否则这不会很有效。谢谢。 - Momonga

@user2007674：当然，这个想法的适用性取决于您间隔的长度。如果您的间隔比字母表中的字符数更短，则重新计算分布将更有效率。 - ssegvic

@Ivaylo：是的，这是相同的想法！ - ssegvic

Answer 3

在数组上执行单次迭代，并针对每个位置记住该位置之前每个字符出现的次数。代码示例如下：

"abcdabc"

对于索引0：

count['a'] = 1
count['b'] = 0
etc...

对于索引1：

....
count['a'] = 1
count['b'] = 1
count['c'] = 0
etc...

对于索引2：

....
count['a'] = 1
count['b'] = 1
count['c'] = 1
....

等等，对于索引 6：

....
count['a'] = 2
count['b'] = 2
count['c'] = 2
count['d'] = 1
... all others are 0

在计算完这个数组后，您可以在常数时间内获取给定字母在区间(i, j)中出现的次数 - 只需计算 count[j] - count[i-1]（注意当=0时要小心！）。

因此，对于每个查询，您将不必遍历区间内的所有字符，而只需遍历最多128个字母（假设您只有ASCII符号）。

缺点是需要更多的内存，具体取决于您使用的字母表大小。

- Ivaylo Strandjev

---

一个缺点 - 根据您使用的字母表大小，您需要更多的内存。对于大小为10^6的字符串来说，这可能是年度低调之一... - crush

这很有道理，而且我的字符串中只有小写字母字符。然而，对于一个长度为10^6的字符串，这将需要大约2600万次操作。这是相当快的，但我想知道是否有更快的解决方案。 - Momonga

对于每个字符串，@IvayloStrandjev？ - crush

@crush，有一个字符串，你想找到其中一个子串中出现最频繁的字符。 - Ivaylo Strandjev

让我们在聊天室里继续这次讨论。 - Ivaylo Strandjev

Answer 4

您需要根据空间和时间复杂度来指定算法要求。

如果您坚持使用O(1)的空间复杂度，只需排序（例如，如果没有自然比较运算符，则使用位的词典序排序）并计算最高元素的出现次数即可获得O(N log N)的时间复杂度。

如果您坚持使用O(N)的时间复杂度，请使用@Luchian Grigore的解决方案，该解决方案还需要O(N)的空间复杂度（对于K字母表来说是O(K)）。

- TemplateRex

---

好的观点，我默认将“最有效率”的概念理解为“最省时”。 - Luchian Grigore

Answer 5

string="something"
arrCount[string.length()];

每次调用 freq() 时访问字符串

freq(char accessedChar){
arrCount[string.indexOf(x)]+=1
}

要获取最常见的字符，请调用 string.charAt(arrCount.max())

- Arpit

Answer 6

假设该字符串是一个常量，并且不同的i和j将被传递到查询出现次数。

如果您想要最小化处理时间，可以进行优化。

struct occurences{
    char c;
    std::list<int> positions;
};

为每个字符保留一个std::list<occurences>，以便快速搜索，您可以保持positions有序。

如果要最小化内存占用，只需保留递增整数并循环遍历i .. j

- Neel Basu

Answer 7

最有效率的算法，正如所建议的那样，是将每个字符的频率存储在一个数组中。然而，请注意，如果您仅使用字符索引数组，则可能会调用未定义的行为。也就是说，如果您正在处理包含代码点超出0x00-0x7F范围的文本（例如使用UTF-8编码的文本），则最好情况下可能会出现分段违规，最坏情况下可能会导致堆栈数据损坏。

char frequncies [256] = {};
frequencies ['á'] = 9; // Oops. If our implementation represents char using a
                       // signed eight-bit integer, we just referenced memory
                       // outside of our array bounds!

一个正确考虑到这一点的解决方案应该类似于以下内容：

template <typename charT>
charT most_frequent (const basic_string <charT>& str)
{
    constexpr auto charT_max = numeric_limits <charT>::max ();
    constexpr auto charT_min = numeric_limits <charT>::lowest ();
    size_t frequencies [charT_max - charT_min + 1] = {};

    for (auto c : str)
        ++frequencies [c - charT_min];

    charT most_frequent;
    size_t count = 0;
    for (charT c = charT_min; c < charT_max; ++c)
        if (frequencies [c - charT_min] > count)
        {
            most_frequent = c;
            count = frequencies [c - charT_min];
        }

    // We have to check charT_max outside of the loop,
    // as otherwise it will probably never terminate
    if (frequencies [charT_max - charT_min] > count)
        return charT_max;

    return most_frequent;
}

如果您想多次迭代相同的字符串，请修改上面的算法（如construct_array）以使用std::array <size_t，numeric_limits <charT> :: max（）- numeric_limits <charT> :: lowest（）+ 1>。然后返回该数组而不是第一个for循环后的最大字符，并省略查找最频繁字符的算法部分。在您的顶层代码中构造一个std::map <std::string，std::array <...>>并将返回的数组存储在其中。然后将查找最频繁字符的代码移动到该顶层代码中，并使用缓存计数数组：

char most_frequent (string s)
{
    static map <string, array <...>> cache;

    if (cache.count (s) == 0)
        map [s] = construct_array (s);
    // find the most frequent character, as above, replacing `frequencies`
    // with map [s], then return it
}

现在，这仅适用于整个字符串。如果您想重复处理相对较小的子字符串，则应改用第一个版本。否则，我认为您最好的选择可能是像第二个解决方案那样将字符串分成可管理的块；这样，您可以从缓存中获取大部分信息，只需在迭代器所在的块中重新计算频率。

- Stuart Olsen

Answer 8

最快的方法是使用unordered_map或类似的数据结构：

pair<char, int> fast(const string& s) {
    unordered_map<char, int> result;

    for(const auto i : s) ++result[i];
    return *max_element(cbegin(result), cend(result), [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; });
}

在编程中，如果要求最轻量级的内存占用，需要一个非常量输入，可以进行排序，这样就可以使用find_first_not_of或类似的函数：

pair<char, int> light(string& s) {
    pair<char, int> result;
    int start = 0;

    sort(begin(s), end(s));
    for(auto finish = s.find_first_not_of(s.front()); finish != string::npos; start = finish, finish = s.find_first_not_of(s[start], start)) if(const int second = finish - start; second > result.second) result = make_pair(s[start], second);
    if(const int second = size(s) - start; second > result.second) result = make_pair(s[start], second);
    return result;
}

需要注意的是，这两个函数都有一个非空字符串的前提条件。此外，如果字符串中最多字符数存在并列情况，则两个函数都将返回字典序最小的字符作为最多字符。

Live Example

- Jonathan Mee