17.10主要元素

(Updated: )
LeetCode

Q

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5  

示例 2：

输入：[3,2]
输出：-1  

示例 3：

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

说明：

你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

A

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//执行用时：
//21 ms, 在所有 Java 提交中击败了12.59%的用户
//内存消耗：
//43.9 MB, 在所有 Java 提交中击败了8.10%的用户

class Solution {
    public int majorityElement(int[] nums) {
        int length = nums.length;
        HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();
        for(int i = 0;i<length;i++){
            if(temp.get(nums[i])==null){
                temp.put(nums[i],1);
            }else{
                temp.put(nums[i],temp.get(nums[i])+1);
            }
            if(temp.get(nums[i])>length/2){
                return nums[i];
            }
        }
        return -1;
    }
}

  • 思路
    遍历列表，将元素重复出现的次数放入map并进行比对,但不符合题目要求空间复杂度O(1)

  • 时间复杂度
    O(N)

  • 空间复杂度
    O(N)

摩尔投票算法

  • 用时最少

执行用时：
1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：
41.6 MB, 在所有 Java 提交中击败了67.28%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//执行用时：
//1 ms, 在所有 Java 提交中击败了100.00%的用户
//内存消耗：
//41.6 MB, 在所有 Java 提交中击败了67.28%的用户

class Solution {
   public int majorityElement(int[] nums) {
	    //记录元素出现次数
        int count = 0;
		//temp，存放需要进行比对的上一个元素
        int k = -1;
        for (int i = 0; i < nums.length; i++) {
			//第一个元素或者说抵消后出现的第一个元素
            if(count == 0){
				//计数1
                count = 1;
				//将元素值存入temp
                k = nums[i];  
            }else{
				//元素重复出现计数加1
                if(k == nums[i]) ++count; 
				//元素不重复抵消一位(减1)
                else --count; 
            }
        }
        
		//若全部抵消，则不存在占比超过一半的元素
        if(count == 0) return -1;
		//验证
        else{
            count = 0;
			//对元素进行计数
            for (int i = 0; i < nums.length; i++) {
                if(k == nums[i]) count++;
            }
			//占比超过一半
            if(2 * count > nums.length){
                return k;
            }else return -1;
        }
    }
}

  • 内存消耗最少
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int majorityElement(int[] nums) {
        int majority = -1;
        int count = 0;
        for(int i = 0; i <  nums.length; i++) {
            if(nums[i] == majority) {
                count++;
            } else {
                if(count == 0) {
                    majority = nums[i];
                    count = 1;
                } else {
                    count--;
                }
            }
        }

        int a = 0; 
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == majority) {
                a++;
            }
        }

        return a > nums.length / 2 ? majority : -1;
    }
}

  • 思路

摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

  • 时间复杂度
    O(2N) = O(N)

  • 空间复杂度
    O(1)