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