dcddc

西米大人的博客

0%

主元素

发表于 更新于 分类于 热度: ℃ 评论: ℃
字数： 305 阅读时长 ≈ 1 分钟
lintcode题目

题目描述

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。

思路

使用贪心。贪心不是一种算法，是一种思想，这种思想告诉我们：

每一步都做出当前最正确的选择以得到最后的结果

遍历数组，用res表示”当前认为”的主元素，用count表示抵消掉竞争对手后，主元素当前剩余的个数
每访问一个元素

  • 如果其和主元素相当，count++
  • 如果不相等，count–，如果count==0，认为当前访问的元素为新的主元素

遍历的过程中，当出现count=0时，也不能保证新的主元素就是真正的主元素。但是，因为主元素严格超过一半，所以遍历完后，res保存的一定是主元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int majorityNumber(ArrayList<Integer> nums) {
        int count = 1;	// 抵消掉竞争对手后剩余的个数
        int res = nums.get(0);	// 始终保存当前出现次数最多的那个元素
        for(int i = 1; i < nums.size(); i++) {
        	if(res == nums.get(i)) {
        		count++;
        	}else {
        		if(count == 0) {
					res = nums.get(i);
					count = 1;
				}
				count--;
				
			}
        }
        return res;
    }

考察点

  • 贪心