PAT甲级 1054. The Dominant Color

题目原文

Behind the scenes in the computer’s memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800×600), you are supposed to point out the strictly dominant color.

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (≤800) and N (≤600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0,2^24). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.

Output Specification:
For each test case, simply print the dominant color in a line.

Sample Input:
5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24

Sample Output:
24

解决思路

这个题目是20分量级的,属于最简单的第一道题,应该要在20分钟内做完。

大概意思就是给一个矩阵,代表一副图片像素点阵,其中如果某个像素值占了所有像素值的一半以上,则称为dominant color,找出给出点阵中的dominant color,而题中标明了所有给的case中一定会有结果存在,所以只需要记录每个像素出现的次数,最后输出出现次数最多的像素值即可。

这题关键在于确定合适的数据结构。如果用一个2^24大小的数组就会极其浪费空间,并且如果要排序获得出现次数最多的像素值效率也极其低下。用map是比较好的选择,不需要开拓包含所有可能像素的空间,只需要每次对对应颜色key的value加一操作即可。最后通过用转换为vector来进行排序,输出排第一的颜色值。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>

// C++字符串和数值转换也包含在里面
// #include <string>
// C++向量
#include <vector>
// map和multimap都在里面
#include <map>
// set和multiset都在里面
// #include <set>
// 各类算法包括排序、查询、最大最小、等等
#include <algorithm>

// 关于数学使用
// #include <cmath>
// 关于字符串和数值类型的转换、随机数、动态内存分配、C的排序等等
// #include <cstdlib>
// 关于C字符串的操作
// #include <cstring>
// 关于数值的最大最小边界的定义
// #include <climits>
// 字符操作
// #include <cctype>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}

int main(void) {
// input
int M, N;
scanf("%d %d", &M, &N);
map<int, int> record;
int pixel;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
scanf("%d", &pixel);
record[pixel]++;
}
}
// handle
vector<pair<int, int> > recordVec(record.begin(), record.end());
sort(recordVec.begin(), recordVec.end(), compare);

// output
cout << (*recordVec.begin()).first;

return 0;
}

后记

后来我想,其实没必要全部都遍历完所有的输入,因为只要某个颜色的出现次数到达了一半,就可以确定这就是结果了,后面的输入就没有必要了,也不用进行排序。但是带来的开销是需要对每一次输入都进行一次判定当前次数,所以我进行了一下性能对比。

以下是算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>

// C++字符串和数值转换也包含在里面
// #include <string>
// C++向量
#include <vector>
// map和multimap都在里面
#include <map>
// set和multiset都在里面
// #include <set>
// 各类算法包括排序、查询、最大最小、等等
#include <algorithm>

// 关于数学使用
// #include <cmath>
// 关于字符串和数值类型的转换、随机数、动态内存分配、C的排序等等
// #include <cstdlib>
// 关于C字符串的操作
// #include <cstring>
// 关于数值的最大最小边界的定义
// #include <climits>
// 字符操作
// #include <cctype>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}

int main(void) {
// input
int M, N;
scanf("%d %d", &M, &N);
map<int, int> record;
int pixel;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
scanf("%d", &pixel);
record[pixel]++;
if(record[pixel] > M * N / 2) {
cout << pixel;
return 0;
}
}
}

return 0;
}

对于之前的输入完后排序,5个case的时间分别是(clang++):3ms, 3ms, 39ms, 13ms, 3ms。空间分别是:512kB, 428kB, 384kB, 864kB, 384kB。

而每次输入都判定当前次数的算法5个case的时间分别是(clang++):4ms, 3ms, 89ms, 12ms, 3ms。空间是:524kB, 516kB, 356kB, 864kB, 492kB。

经过多次提交测试,其实两种算法的差别基本不大。当然也可能与数据规模有关,受限于测试数据,没办法深入测试了。