时间戳

首页 > 解决方案 > 为什么排序数组中的中间元素是多数元素？

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

问题描述

我在 leetcode中做这个问题。

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

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

我想问的是

“为什么排序数组中的中间元素是多数元素？”

有人可以解释这件事吗？

这个问题的要求：

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

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

这是答案的代码： 

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

标签： javascriptarrays

解决方案

假设输入的数组有一个多数元素，它会在数组中至少出现(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 的数组，但同样的想法适用于任何大小的数组。

推荐阅读