面试题 17.10. Find Majority Element LCCI

1. Question

A majority element is an element that makes up more than half of the items in an array. Given a integers array, find the majority element. If there is no majority element, return -1. Do this in O(N) time and O(1) space.

2. Examples

Example 1:

Input: [1,2,5,9,5,9,5,5,5]
Output: 5

Example 2:

Input: [3,2]
Output: -1

Example 3:

Input: [2,2,1,1,1,2,2]
Output: 2

3. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-majority-element-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

4. Solutions

class Solution {
  public int majorityElement(int[] nums) {
    // moore投票法

    int cand = 0;
    int count = 0;

    // 首先进行遍历，相同的话count+1，不同的话就count--进行抵消，到0时候指定新的候选者

    for(int num : nums) {
      if(count == 0) {
        cand = num;
      }
      if(num == cand) {
        count++;
      } else {
        count--;
      }
    }

    // 计数，查看候选者的数量是否超过条件要求的数量

    count = 0;
    for(int num : nums) {
      if(num == cand) {
        count++;
      }
    }

    return count * 2 >= nums.length ? cand : -1;
  }
}