PAT 解题报告 1054. The Dominant Color (20)

题目描述:

就是给一张图, 让你统计这张图里面某个颜色(用整数表示)超过所有颜色数一半的那个颜色

算法分析:

最容易想到应该就是直接暴力做吧, 线性扫描, 统计每种颜色的个数, 一旦碰到超过总数一半的那个颜色, 就停止输出即可. 我这里没用这种方法, 一个是我觉得颜色是用整数表示的, 用哈希表之类的这个counter数量太大(内存消耗很大).

我提供另一种比较奇怪的思路: 所有的整数排序, 然后用一个长度是 n/2 +1 的window去套这个排好序的序列, 一旦碰到某个整数在这个window里面的头尾都是一样的整数值, 那么这个整数就一定是我们的dominant color,因为题目中说明了这样的color一定存在, 所以此法可行. 不然这个方法一般不适用.

注意点:

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 7, 2013