为什么排序数组中的中间元素是主要元素？

Question

我在LeetCode做这道题，看到了一种我理解不了的解法。

解法是："将数组排序，数组中间的元素就是多数元素"。

我想问的是：

"为什么一个已排序数组的中间元素就是多数元素？"

有人可以解释一下吗？

这个问题的要求：

给定一个大小为n的数组，找到其中的多数元素。即出现次数超过 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且多数元素总是存在于数组中。

Here is the answer's code:

var majorityElement = function(nums) {
    // sort the array and the middle is the majority
    nums.sort((a,b) => a - b);
    return nums[Math.floor(nums.length/2)];
}; 
console.log(majorityElement([3,2,3]))
console.log(majorityElement([2,2,1,1,1,2,2]))

- Jacky

---

我认为你错过了计数，大多数元素始终超过元素的一半（n/2）。 - Estradiaz

Answer 1

假设输入的数组包含大多数元素，则该元素在数组中至少出现(n / 2) + 1次。如果大多数元素是数组中的最小数字，则排序后的数组将如下所示：

Original Answer

MMMMXX
  ^^ mid (even)

或者

MMMMMXXX
    ^ mid (odd)

其中M是主要元素，X代表任何其他元素。正如您所看到的，M将始终落在数组的中间。如果主要元素是数组中的最高数字，则它将类似于：

即使没有排序，也可以通过Boyer-Moore投票算法找到主要元素。

该算法的基本思想是从头到尾遍历数组，使用一个计数器来记录当前元素出现的次数，如果下一个元素与其相同，则计数器加1，否则计数器减1。如果计数器为0，则将下一个元素作为候选主要元素，并继续遍历数组。在遍历完成后，最后一个候选主要元素即为主要元素。

XXMMMM
  ^^ mid (even)

或者

XXXMMMM
    ^ mid (odd)

最初的回答中，M 仍然在中间。

如果 M 不是数组中最高或最低的元素，则无论您如何尝试移动范围，排序后的数组仍将在中间具有 M：

XXMMMM
XMMMMX
MMMMXX
  ^^

或者

XXXMMMM
XXMMMMX
XMMMMXX
MMMMXXX
   ^

这些示例仅适用于长度为6和7的数组，但相同的思想也适用于任何大小的数组。

原始答案：Original Answer

- CertainPerformance

Answer 2

这是我的理解。

假设相反，中间元素不是主要元素。 因此，主要元素要么在中间元素的左边，要么在右边。 左边有⌊ n/2 ⌋个元素，右边有n - ⌊ n/2 ⌋个元素。

由于主要元素是出现次数超过⌊ n/2 ⌋的元素，它既不能只在中间元素的左边，也不能只在右边，因为两边都是<= ⌊ n/2 ⌋，而且由于存在主要元素，因此必须包括中间元素。

- hsnsd

Answer 3

原因是如果数组中有一个元素出现次数超过n/2次，那么在对数组进行排序后，中间点会经过该元素，因此它们返回索引n/2处的值。

- Vengatesh Subramaniyan