面试题 17.10. 主要元素

题目

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

示例1：

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

示例2：

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

示例3：

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

解法

解法一：

Java

public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (candidate == num) {
                count++;
            } else {
                count--;
            }
        }
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        if (count > nums.length / 2) {
            return candidate;
        } else {
            return -1;
        }
    }