首页 » 技术分享 » 多数投票算法 Majority Vote Algorithm

多数投票算法 Majority Vote Algorithm

　
评论关闭　672次浏览

题目如下:

Write a program to find the element in an array that is repeated more than half number of times. Return -1 if no such element is found.

分析如下：

最容易想到的办法是，用一个hash或者map去统计每个元素的出现次数，然后得出答案。时间复杂度为O(N)空间复杂度也为O(N)。
另外一个经典算法可以降低空间复杂度，Majority Vote Algorithm。分为两步进行，第一步，找到出现次数最多的元素，即majority element；第二步，如果majority element出现的次数大于总元素数量的一半，就返回它，否则返回-1。

我的代码:

char find_more_than_half_shown_number(char* arr, int len){
    int i=0;
    std::vector<int> vec;
    while(i<len){
        if(vec.empty()){     //如果是第一次记录，把当前majority数设定为数组的第一个元素
            vec.push_back(arr[i]);
            vec.push_back(1);
        }else if(vec[0]==arr[i]){ //如果数组扫描到的数和当前majority数相等。
            vec[1]++;
        }else if(vec[0]!=arr[i]&&vec[1]!=0){//如果数组扫描到的数和当前majority数不相等，且当前majority数的票数至少有一票。
            vec[1]--;
        }else{                   //如果数组扫描到的数和当前majority数不相等，且当前majority数的票数有零票，那么就该更换majority数了。
            //条件等价于(vec1[0]!=arr[i]&&vec1[1]==0)
            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) //检验majority数的票数是否超过了总票数的一半
        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;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：多数投票算法 Majority Vote Algorithm，转载请注明来源！

赞 0