6

我有一串s长度n。用于查找范围内最频繁字符的最有效数据结构/算法是i..j什么？

字符串不会随着时间而改变，我只需要重复查询s[i], s[i + 1], ... ,中最常见的字符s[j]。

4

8 回答 8

10

一个数组，其中保存每个字符的出现次数。您在遍历字符串一次时增加相应的值。这样做时，您可以记住数组中的当前最大值；或者，在最后的数组中查找最高值。

伪代码

arr = [0]
for ( char in string )
   arr[char]++
mostFrequent = highest(arr)
于 2013-01-24T13:53:01.107 回答
2

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

Python 中的一些伪代码如下。我假设您的字符是字符，因此有 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
于 2013-01-24T13:57:55.733 回答
2

对数组进行一次迭代，并为每个位置记住每个字符在该位置之前出现的次数。所以是这样的：

"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]（这里小心i = 0！）。

因此，对于每个查询，您必须遍历所有字母而不是间隔中的所有字符，因此您最多只能通过 128 个字符而不是遍历 10^6 个字符（假设您只有 ASCII 符号）。

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

于 2013-01-24T14:01:16.010 回答
1

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

如果您坚持O(1)空间复杂性，那么仅排序（例如，如果没有可用的自然比较运算符，则使用位的字典顺序）并计算最高元素的出现次数会给您带来O(N log N)时间复杂度。

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

于 2013-01-24T16:00:43.547 回答
0 
string="something"
arrCount[string.length()];

在每次访问字符串调用 freq() 之后

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

获得最频繁的 char 调用string.charAt(arrCount.max())

于 2013-01-24T14:07:34.380 回答
0

正如已经建议的那样，最省时的算法是将每个字符的频率存储在一个数组中。但是请注意，如果您只是用字符索引数组，您可能会调用未定义的行为。即，如果您正在处理包含 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;
}

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

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
}

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

于 2013-01-24T17:32:51.603 回答
0

假设字符串是恒定的，并且不同i，并且j将被传递给查询出现。

如果你想最小化处理时间，你可以做一个

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

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

如果你想最小化内存，你可以保持一个递增的整数并循环遍历i..j

于 2013-01-24T14:08:51.953 回答
0

最快的方法是使用一个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

于 2018-12-06T16:06:34.747 回答