Example 21
多数元素
题目概述：给定一个大小为 n 的数组nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于[
]的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例1：
输入：nums = [3,2,3]
输出：3
示例2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
解题思路：是如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为[]的元素（下标从 0 开始）一定是众数。
对于这种算法，先将 nums 数组排序，然后返回上文所说的下标对应的元素。下面的图中解释了为什么这种策略是有效的。在下图中，第一个例子是n 为奇数的情况，第二个例子是n 为偶数的情况。
对于每种情况，数组下面的线表示如果众数是数组中的最小值时覆盖的下标，数组上面的线表示如果众数是数组中的最大值时覆盖的下标。对于其他的情况，这条线会在这两种极端情况的中间。对于这两种极端情况，它们会在下标为[]的地方有重叠。因此，无论众数是多少，返回[]下标对应的值都是正确的。
解题步骤：
1. 将数组排序。
2. 将排序后的数组中的索引为[]的元素返回，其一定是数组中的多数元素。
示例代码如下：
public class MostElements { /** * 给定一个大小为 n 的数组nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 * 示例1： * 输入：nums = [3,2,3] * 输出：3 * 示例2： * 输入：nums = [2,2,1,1,1,2,2] * 输出：2 * 来源：力扣（LeetCode） * 链接：https://leetcode.cn/problems/majority-element */ public static void main(String[] args) { MostElements me = new MostElements(); System.out.println(me.majorityElement(new int[]{3, 2, 3})); // 3 } /** * 官方 * * @param nums * @return */ public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; } }
