【leetcode】229. 求众数 II

技术文章 11个月前 完美者
1,189 0

标签:style   date   cal   code   color   --   return   投票   continue   

 

int* majorityElement(int* nums, int numsSize, int* returnSize){
    int* res =(int*)calloc(2,sizeof(int));
    *returnSize=0;
    if (nums == NULL || numsSize == 0) return res;
    // 初始化两个候选人candidate,和他们的计票
    int cand1 = nums[0], count1 = 0;
    int cand2 = nums[0], count2 = 0;
    int i;
    // 摩尔投票法,分为两个阶段:配对阶段和计数阶段
    // 配对阶段
    for (i=0; i<numsSize; i++) {
        // 投票
        if (cand1 == nums[i]) {
            count1++;
            continue;
        }
        if (cand2 == nums[i]) {
            count2++;
            continue;
        }
        
        // 第1个候选人配对
        if (count1 == 0) {
            cand1 = nums[i];
            count1++;
            continue;
        }
        // 第2个候选人配对
        if (count2 == 0) {
            cand2 = nums[i];
            count2++;
            continue;
        }
        
        count1--;
        count2--;
    }
    
    // 计数阶段
    // 找到了两个候选人之后,需要确定票数是否满足大于 N/3
    count1 = 0;
    count2 = 0;
    for (i=0; i<numsSize; i++) {
        if (cand1 == nums[i]) count1++;
        else if (cand2 == nums[i]) count2++;
    }
    
    if (count1 > numsSize / 3) 
        res[(*returnSize)++]=cand1;
    if (count2 > numsSize / 3)
        res[(*returnSize)++]=cand2;
    
    return res;
}

 

【leetcode】229. 求众数 II

标签:style   date   cal   code   color   --   return   投票   continue   

原文地址:https://www.cnblogs.com/ganxiang/p/14202214.html

版权声明:完美者 发表于 2021-01-01 12:50:50。
转载请注明:【leetcode】229. 求众数 II | 完美导航

暂无评论

暂无评论...