首页 > 试题广场 >

The Dominant Color (20)

[编程题]The Dominant Color (20)

热度指数：3890 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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, 800x600), you are supposed to point out the strictly dominant color.

输入描述:

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²⁴).  It is guaranteed that the strictly dominant color exists for each input image.  All the numbers in a line are separated by a space.

输出描述:

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

示例1

输入

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

输出

算法知识视频讲解

Python

:P）

python一开始list会超时，改成dict

m, n = map(int, input().split())
clr = {}
# 字典是O(1),比list要快很多，把存储结构换成字典
th = m * n / 2
th1 = m * n
while len(clr) != th1:
    cur = input().split()
    for i in cur:
        if clr.get(i, -1) != -1:
            clr[i] += 1
        else:
            clr[i] = 1
    l = sorted(clr.items(), key=lambda x: x[1], reverse=True)
    if l[0][1] > th:
        print(l[0][0])
        break


# 原来的，最后两个测试点会超时
# m, n = map(int, input().split())
# clr = []
# th = m * n / 2
# th1 = m * n
# while len(clr) != th1:
#     # cur = list(map(int, input().split()))
#     cur = [int(i) for i in input().split()]
#     clr.extend(cur)
#     tmp_s = set(cur)
#     cnt = [(clr.count(i), i) for i in tmp_s]
#     if max(cnt)[0] > th:
#         print(max(cnt)[1])
#         break

发表于 2021-07-11 15:41:48 回复(0)