PAT-ADVANCED1054——The Dominant Color

我的PAT-ADVANCED代碼倉：https://github.com/617076674/PAT-ADVANCED

原題連結：https://pintia.cn/problem-sets/994805342720868352/problems/994805422639136768

題目描述：

題目翻譯：

1054 主色彩

在計算機記憶體的幕後，顔色總是被稱為每個像素的一系列24位資訊。 在圖像中，具有最大比例區域的顔色稱為主色。 嚴格主色是指其主色占總面積的一半以上。 現在給出分辨率M乘N的圖像（例如，800×600），你應該指出嚴格主色。

輸入格式：

每個輸入檔案包含一個測試用例。 對每個測試用例，第一行包含2個正數：M（<= 800）和N（<= 600），它們是圖像的分辨率。 然後是N行，每行包含[0, 2]範圍内的M個數字顔色（數字顔色在[0, 2 ^ 24)範圍内）。題目保證每個輸入圖像都存在嚴格主色。 一行中的所有數字都用空格分隔。

輸出格式：

對每個測試用例，在一行中簡單輸出其主色。

輸入樣例：

5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24
           

輸出樣例：

24
           

知識點：計數

思路：用map集合來計算每種顔色的數量

時間複雜度是O(M * N)。空間複雜度是O(n)，其中n為輸入不同顔色數。

C++代碼：

#include<iostream>
#include<map>

using namespace std;

int main(){
	int M, N;
	scanf("%d %d", &M, &N);
	int num;
	map<int, int> numMap;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			scanf("%d", &num);
			numMap[num]++;
		}
	}
	int max = 0;
	int dominant = -1;
	for(map<int, int>::iterator it = numMap.begin(); it != numMap.end(); it++){
		if(it->second > max){
			dominant = it->first;
			max = it->second;
		}
	}
	printf("%d\n", dominant);
	return 0;
} 
           

C++解題報告：