题目

https://leetcode-cn.com/problems/majority-element/

题解

var majorityElement = function(nums) {
    const half = nums.length / 2
    let map = new Map()
    for(let item of nums) {
        if (map.get(item) === undefined) {
            map.set(item, 1)
        } else {
            map.set(item, map.get(item) + 1)
        }
        // 重新get一次
        if (map.get(item) > half) {
            return item
        }
    }
    return 0
};

思路

使用一个Map对象存储出现的元素和次数, 当一个元素的出现次数>=数组的一半的时候 返回这个元素

参考

1. 对象法：使用对象存储对应的元素和次数，和我的解题类似(我的是map对象)

   • 时间复杂度: O(n) 遍历一次
   • 空间复杂度: O(n) obj中属性最多为 n/2 个

     var majorityElement = function(nums) {
     let half = nums.length / 2
     let obj = {}
     for(let num of nums){
      obj[num] = (obj[num] || 0) + 1
      if(obj[num] > half) return num
     }
     };

2. 排序法：但是很多面试题不允许使用这些现有的方法

   • 时间复杂度 O(nlogn) 使用了快速排序
   • 空间复杂度 O(1) 原地修改数组

     var majorityElement = function(nums) {
     nums.sort((a,b) => a - b)
     return nums[Math.floor(nums.length / 2)]
     };

3. 栈方法：当 元素和栈顶元素相等 或 空栈 时入栈，否则出栈。最后栈中剩下的必然都是是大于一半的那个元素

   • 时间 O(n) 循环一次nums
   • 空间 O(n)

     var majorityElement = function(nums) {
     let stack = []
     for(let n of nums){
     let m = stack.length
     if(stack[m - 1] === n || !m){
      stack.push(n)
     } else {
      stack.pop()
     }
     }
     return stack[0]
     };