LeetCode:Majority Element

Posted on | Edited on | In


[LeetCode题解]169 Majority Element

题目

思路01

1.用最简单的方法。先用Arrays的sort方法把数组排序，再返回数组的中间的数。
时间复杂度 O(NlogN) 空间复杂度 O(1)。

1
2
3
4
5
6
7
8
public class MajorityElement01 {
    public static int majorityElement(int[] nums){
        if (nums.length == 0 || nums == null)
            return 0;
        Arrays.sort(nums);
        return nums[nums.length / 2] ;
    }
}

思路02

2.哈希表法。把数组的每个数值和该数值的出现次数分别以键值对的形式存入哈希表中。当某数出
现次数大于数组的元素个数时，返回该数字。
时间复杂度 O(N) 空间复杂度 O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class MajorityElement02 {
    public static int majorityElement(int[] nums){
        if (nums.length == 0 || nums == null)
            return 0;
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        int res = 0;
        for (int i = 0; i < nums.length ; i++) {
            if (!map.containsKey(nums[i]))
                map.put(nums[i],1);
            else
                map.put(nums[i],map.get(nums[i]) + 1);
            if (map.get(nums[i]) > nums.length / 2){
                res = nums[i];
                break;
            }
        }
        return res;
    }
}

思路03

3.Moore投票算法。是由德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明的。该算法的主要思想是假设e是出现次数大于n/2的数字，那么将所有非e的数字和e成对地两两相消，最后剩下来的数字绝对是e.
过程：初始化最终返回值res为num[0],计数count为0.从左往右逐个遍历数组元素，如果与num[0]相等，则count加一。否则count减一。当count为0时,把res赋值为num[i+1].遍历结束后返回res.
时间复杂度 O(N) 空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class MajorityElement03 {
    public static int majorityElement(int[] nums){
        if (nums.length == 0 || nums == null)
            return 0;
        int res = nums[0];int count = 1;
        for (int i = 1; i < nums.length ; i++) {
            if (res == nums[i])
                count++;
            else
                count--;
            if (count == 0)
                res = nums[i + 1];
            continue;
        }
        return res;
    }
}