线性时间投票算法。我不明白

该算法仅在集合中有大多数元素(超过一半的元素是相同的)时才起作用。 AAACCBB 在你的例子中没有这样的多数。最常见的字母出现3次,字符串长度为7。

这是对其他解释的一个重要补充。摩尔的投票算法有两部分-

1. 运行摩尔投票算法的第一部分 只给你一个候选人 对于大多数元素。注意这里的“候选人”。

2. 在第二部分,我们需要 再次迭代数组 以确定此候选项是否出现最大次数(即大于大小/2次)。

第一次迭代是为了找到候选的&second迭代是为了检查这个元素在给定数组中是否经常出现。

因此,时间复杂性是: O(n) + O(n) ≈ O(n)

从第一个链接的SO问题开始:

其属性是数组中超过一半的项等于n

从Boyer和Moore页面:

如果存在这样的元素,那么序列中的哪个元素占大多数

这两种算法都明确地假设一个元素发生 至少N/2次 . (特别注意,“多数”与“最常见”不同。)

我为这个算法编写了一个C++代码

char find_more_than_half_shown_number(char* arr, int len){
int i=0;
std::vector<int> vec;
while(i<len){
    if(vec.empty()){     
        vec.push_back(arr[i]);
        vec.push_back(1);
    }else if(vec[0]==arr[i]){ 
        vec[1]++;
    }else if(vec[0]!=arr[i]&&vec[1]!=0){
        vec[1]--;
    }else{                   
        vec[0]=arr[i];
    }
    i++;
}
int tmp_count=0;
for(int i=0;i<len;i++){
    if(arr[i]==vec[0])
        tmp_count++;
}
if(tmp_count>=(len+1)/2)
    return vec[0];
else
    return -1;
}

主要功能如下:

int main(int argc, const char * argv[])
{
    char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'};
    int len=sizeof(arr)/sizeof(char);
    char rest_num=find_more_than_half_shown_number(arr,len);
    std::cout << "rest_num="<<rest_num<<std::endl;
    return 0;
}

当测试用例为“aaaccbb”时,集合没有多数。因为“aaaccbb”的长度为7,所以没有任何元素出现超过3次。

以下是“Boyer和Moore线性时间投票算法”的代码:

int Voting(vector<int> &num) {
        int count = 0;
        int candidate;

        for(int i = 0; i < num.size(); ++i) {
            if(count == 0) {
                candidate = num[i];
                count = 1;
            }
            else
                count = (candidate == num[i]) ? ++count : --count;
        }
        return candidate;
    }