Leetcode 题目解析之 Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

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

A Linear Time Majority Vote Algorithm 一个典型的算法，可以在一次遍历，时间复杂度是O(1)，空间复杂度是O(1)的情况下完成。

代码语言：txt复制

    public int majorityElement(int[] nums) {
        int m = nums[0];
        int c = 1;
        for (int i = 1; i < nums.length; i  ) {
            if (m == nums[i]) {
                c  ;
            } else if (c > 1) {
                c--;
            } else {
                m = nums[i];
            }
        }
        return m;
    }

algorithm element size time 遍历

0 人点赞