[TIOJ] 1160. 3.動態眾數問題

題目連結:http://tioj.infor.org/problems/1160
其實只要記錄每個數字有多少個,跟紀錄一下當前的眾數是誰以及他的量,當插入一個數字使得他的數量大於原本的眾數時就更新一下眾數資訊,不過不能用array因為他的值域太大,所以不妨考慮用個hash_table(unordered_map)
#include <stdio.h>
#include <unordered_map>

using namespace std;

int main(){
	unordered_map<int, int> arr;
	int inp, which=0, size=0;
	scanf("%d",&inp);
	while(inp!=0){
		if(arr.find(inp) == arr.end()){
			arr[inp] = 1;
		}else{
			arr[inp] ++;
		}
		if(arr[inp]>size){
			which = inp;
			size = arr[inp];
		}else if(arr[inp]==size){
			which = (inp<which)?inp:which;
		}
		printf("%d %d\n",size, which);
		scanf("%d",&inp);
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1902. 「殿仁.王,不認識,誰啊?」,然後他就死了……

[NPSC] 2009初賽 E. 檸檬汽水傳說

[AtCoder] [經典競程 90 題] 024 - Select +/- One(★2)