46. 主元素

描述

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。

注意事项

You may assume that the array is non-empty and the majority number always exist in the array.

样例

给出数组 [1,1,1,1,2,2,2] ，返回 1

挑战

要求时间复杂度为O(n)，空间复杂度为O(1)

代码

1. 快速排序 O(n)
   思路
   一个元素出现次数大于所有元素个数的二分之一，则中间位置元素必然是这个元素

public class Solution {
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(List<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return -1;
        }
        int length = nums.size() - 1;
        // 注意第 k 个数，k 是从 1 开始的
        return quickSelect(nums, 0, length, length / 2 + 1);
    }
    
    private int quickSelect(List<Integer> nums,
                            int start,
                            int end,
                            int k) {
        if (start >= end) {
            return nums.get(start);
        }
        int left = start;
        int right = end;
        int pivot = nums.get(left + (right - left) / 2);
        
        while (left <= right) {
            while (left <= right && nums.get(left) < pivot) {
                left++;
            }
            while (left <= right && nums.get(right) > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = nums.get(left);
                nums.set(left, nums.get(right));
                nums.set(right, temp);
                left++;
                right--;
            }
        }
        
        // 此处 k - 1 即表示 k 是从 1 开始的
        if (start + k - 1 <= right) {
            return quickSelect(nums, start, right, k);
        } else if (start + k - 1 >= left) {
            return quickSelect(nums, left, end, k - left + start);
        } else {
            return pivot;
        }
    }
}

2. 基于数组特点的 O(n)
   思路
   数组中主元素的出现次数必然大于其余所有元素出现次数，所以数组中当前元素如果与上一元素相同 count 加1，不同时 count 减1，count 为 0 时将当前元素设为主元素备选值，则遍历数组主元素备选值的最终值即为主元素的值

public class Solution {
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(List<Integer> nums) {
        int count = 0;
        int candidate = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (count == 0) {
                count = 1;
                candidate = nums.get(i);
            } else if (candidate == nums.get(i)) {
                count++;
            } else {
                count--;
            }
        }
        
        return candidate;
    }
}