Leetcode 题目解析之 Majority Element

原创

ruochen

发布于 2022-02-14 12:14:50

1.2K0

发布于 2022-02-14 12:14:50

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.

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

    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;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

element