列表

详情


OR110. 查找数组众数

描述

给定一个数组A[n], 定义数组的众数 ( Majority Element) 为数组中出现次数超过 n/2 次的元素, 假设数组A[n]非空且一定存在众数, 请设计算法找到该众数并输出.

输入描述

一个非空且一定存在众数的整数数组,如: [1,2,2]

输出描述

输出打印该众数,如: 2

示例1

输入:

[1,2,2]

输出:

2

示例2

输入:

[3,1,-2,3,1,3,3]

输出:

3

原站题解

C++14 解法, 执行用时: 1ms, 内存消耗: 364KB, 提交时间: 2020-01-10

#include<stdio.h>
int main()
{
    int m, n, k = 0;
    char ch;
    scanf("%c", &ch);
    while (scanf("%d,", &m))
    {
        if (m != '[' || m != ']')
        {
            if (k == 0)
                n = m;
            k += (m == n ? 1 : -1);
        }
    }
    printf("%d\n", n);
}

C 解法, 执行用时: 2ms, 内存消耗: 240KB, 提交时间: 2020-03-18

#include<stdio.h>

int main()
{
    int a[1000];
    int i=0;
    getchar();
    while(1){
        scanf("%d",&a[i++]);
        if(getchar()==']')
            break;
    }
    int num=i;
    for(i=0;i<num;i++){
        int flag=a[i];
        int count=0;
        for(int j=0;j<num;j++){
            if(a[j]==flag)
                count++;
        }
        if(count>num/2)
            break;
    }
    printf("%d",a[i]);
        
    return 0;
}

上一题