javascript - 为什么排序数组中的中间元素是多数元素？

Question

我在做 this question在 leetcode 中。

我看到了一个我无法理解的解决方案

它说“对数组进行排序，中间的为多数”

我想问的是

"Why the middle element in a sorted array is the majority element?"

有人能解释一下吗？

本题要求:

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.

这是答案的代码:

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]))

Answer 1

假设输入的数组有个多数元素，它在数组中至少会出现(n/2) + 1次。如果多数元素是数组中最小的数，则排序后的数组将类似于:

MMMMXX
  ^^ mid (even)

或

MMMMMXXX
    ^ mid (odd)

其中 M 是多数元素，X 代表任何其他元素。如您所见，M 将始终落在数组的中间。如果多数元素是数组中的最高数，则它看起来像:

XXMMMM
  ^^ mid (even)

或

XXXMMMM
    ^ mid (odd)

M 仍在中间。

如果 M 既不是数组中最高的元素也不是最低的元素，那么排序后的数组中间仍然有 M，无论您如何尝试移位范围:

XXMMMM
XMMMMX
MMMMXX
  ^^

或

XXXMMMM
XXMMMMX
XMMMMXX
MMMMXXX
   ^

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