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; }