博客

题目描述

题目来源：

https://leetcode-cn.com/problems/majority-element/


给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

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

package leetcode;

import java.util.Arrays;

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums); // 排序
        int result = 0;    // 结果
        int numsCount = 0; // 记录最大一次数组相同元素的个数和
        int cur = 0;       // 记录每一次数组相同元素的个数和
        int i;

        // 遍历一遍数组
        for (i=0; i<nums.length-1; i++) {
            cur++; // 数组相同元素的个数 +1
            // 记录最大一次数组相同元素的个数和（随数组遍历不断变化）
            if (numsCount < cur) {
                numsCount = cur;
                result = nums[i]; // 结果在最大一次数组相同元素的个数和的数组元素中
            }

            // 在不相等的数组元素的地方作为一个断点
            if (nums[i] != nums[i+1]) {
                cur = 0;
            }
        }

        // 处理最后一个数
        cur++;
        if (numsCount < cur) {
            numsCount = cur;
            result = nums[i];
        }

        return result;
    }
}

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2,2,1,1,1,2,2};
        System.out.println(solution.majorityElement(nums));
    }
}

通过LeetCode的测试用例：