LeetCode精选TOP面试题169. 多数元素_给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于

题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
输入: [3,2,3]
输出: 3
1
2
3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
1
2
3

解题思路

根据题目描述，给定的数组总是存在多数元素，而多数元素的定义指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
那么这个题就很容易想了，直接排序，排序后返回数组中下标是nums.length / 2 的元素即可。要保证其出现次数大于 ⌊ n/2 ⌋ ，那么这个数肯定横跨在nums.length / 2 的左右，不管nums.length是奇数还是偶数。
举个例子：

• nums.length 是 6 的时候，多数元素出现的次数肯定大于⌊ 6 / 2 ⌋ = 3，也就是出现的次数 ≥ 4 ，那么这个多数元素肯定会出现在排序后数组的 中间位置2 和 3上，很容易理解。
• nums.length 是 7 的时候，多数元素出现的次数肯定大于⌊ 7 / 2 ⌋ = 3，也就是出现的次数 ≥ 4 ，那么这个多数元素肯定会出现在排序后数组的中间位置 （3 和4）或者 （4 和5）上，也很容易理解。

代码（Java）

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums); // 排序
        return nums[nums.length/2];// 返回结果
    }
}
1
2
3
4
5
6