SPOJ-MAJOR : Majority
問題概要
長さN(<10^6)の配列が与えられる。要素は[-L, L](L=3000)に含まれる。過半数回以上出現する値があればそれを出力する問題。
解法
各数が何回出現したかを数えておくだけ。
acceptされたコード
計算量O(N + L)。
#include <cstdio> #include <cstring> using namespace std; const int MAX_W = 1000; int instance[MAX_W * 2 + 1]; int *xs; int main(){ int T; scanf("%d", &T); xs = instance + MAX_W; while(T--){ int N; memset(instance, 0, sizeof(instance)); scanf("%d",&N); for(int i=0, x; i<N; i++){ scanf("%d",&x); xs[x]++; } int ans = MAX_W + 1; for(int i=-MAX_W; i<=MAX_W; i++){ if(xs[i] >= N/2+1){ ans = i; } } if(ans == MAX_W + 1){ puts("NO"); } else{ printf("YES %d\n", ans); } if(T>0){ puts(""); } } return 0; }