给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
方法一：哈希表
时间复杂度O(n)，空间复杂度O(n)
/**
* @param {number[]} nums
* @return {number}
*/
majorityElement = function(nums) {
let hash = {}
let majority_element
let max_num = 0
for (let num of nums) {
if (hash[num]) {
hash[num]++
} else {
hash[num] = 1
}
if (hash[num] > max_num) {
max_num = hash[num]
majority_element = num
}
}
return majority_element
}
方法二：排序
排完续中间的数就是众数，复杂度取决于排序的复杂度
majorityElement = function(nums) {
let _nums = nums.sort((a, b) => a - b)
let majority_element = _nums[Math.floor(nums.length / 2)]
return majority_element
}
方法三：随机化
因为超过 n/2 的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。
时间复杂度O(n)，空间复杂度O(1)
majorityElement = function(nums) {
let majority_element
while (majority_element === undefined) {
let random = Math.random()
let length = nums.length
let random_index = Math.floor(random * length)
let element = nums[random_index]
let count = 0
for (let num of nums) {
if (num == element) {
count++
}
}
console.log(count)
if (count >= length / 2) {
majority_element = element
}
}
return majority_element
}
方法四：分治算法
我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。
时间复杂度O(nlogn),空间复杂度O(logn)
majorityElement = function(nums) {
function majority_element_rec(first_idx, last_idx) {
if (first_idx == last_idx) {
return nums[first_idx]
}
let mid = Math.floor((last_idx - first_idx) / 2) + first_idx
let left = majority_element_rec(first_idx, mid)
let right = majority_element_rec(mid + 1, last_idx)
if (left == right) {
return left
}
let left_count = 0
let right_count = 0
for (var i = first_idx; i <= mid; i++) {
if (nums[i] == left) {
left_count++
}
}
for (var j = mid + 1; j <= last_idx; j++) {
if (nums[j] == right) {
right_count++
}
}
return left_count > right_count ? left : right
}
return majority_element_rec(0, nums.length - 1)
}
方法五：投票算法
如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
时间复杂度O(n)，空间复杂度O(1)
majorityElement = function(nums) {
let majority_element = null
let count = 0
for (let num of nums) {
if (count == 0) {
majority_element = num
}
if (num != majority_element) {
count--
} else {
count++
}
}
return majority_element
}
最后给出测试用例
let nums = [1, 1, 2, 2, 3, 3, 2, 2, 2, 4, 2]
console.log('result>>>', majorityElement(nums))
// result 2
