給定一個大小為 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
}
方法二：排序
排完續(xù)中間的數就是眾數榕订，復雜度取決于排序的復雜度
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 的子數組中唯一的數顯然是眾數歹嘹，直接返回即可届慈。如果回溯后某區(qū)間的長度大于 1，我們必須將左右子區(qū)間的值合并憔辫。如果它們的眾數相同鸯檬，那么顯然這一段區(qū)間的眾數是它們相同的值。否則螺垢，我們需要比較兩個眾數在整個區(qū)間內出現的次數來決定該區(qū)間的眾數喧务。
時間復雜度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
