MajorityElement(众数)

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

1
2
输入: [3,2,3]
输出: 3

示例 2:

1
2
输入: [2,2,1,1,1,2,2]
输出: 2

解题思路1：

暴力法，时间复杂度是O(n^2)，超出时间限制了@_@…

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int majorityElement(int[] nums) {
    int count = 0;
    for (int num1 : nums) {
        for (int num2 : nums) {
            if (num1 == num2) {
                count++;
                if (count > nums.length / 2) return num1;
            }
        }
        count = 0;
    }
    return nums[0];
}

解题思路2：

想不出，只好参考评论了。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int majorityElement(int[] nums) {
    int count = 1;
    int i = nums[0];
    for (int num : nums) {
        if (i == num) count++;
        else {
            count--;
            if (count == 0) {
                i = num;
                count = 1;
            }
        }
    }
    return i;
}

总结：

众数最分散的分布是每两个中的(majority,xxx)或者(xxx,majority)，最后还剩下一个(majority)，个人拙见，勿笑…