44 - 求众数

题目

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3] 输出: 3

示例 2:

输入: [2,2,1,1,1,2,2] 输出: 2

解答

首先想到的就是穷举，每个数记录一下出现的次数，然后把最大的数贴出来。

既然有了数组，也可以排序一下，再做计算。

穷举

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let count = {}
  nums.map(e => {
    if (e in count) {
      count[e]++
    } else {
      count[e] = 1
    }
  })
  let keys = Object.keys(count)
  for (const key of keys) {
    if (count[key] > Math.floor(nums.length / 2)) {
      return key
    }
  }
};

Runtime: 60 ms, faster than 81.84% of JavaScript online submissions for Majority Element.

Memory Usage: 38 MB, less than 28.57% of JavaScript online submissions for Majority Element.

不知道为啥本地测试环境一直不通过。。明明想要的是3，给的也是3啊。。😂😂

image-20190808210522702

func majorityElement(nums []int) int {
    count := make(map[int]int)
    for _, elem := range nums {
        if _, ok := count[elem]; ok {
            count[elem]++
        } else {
            count[elem] = 1
        }
        runtime.Gosched()
    }
    for key, val := range count {
        if val > len(nums)/2 {
            return key
        }
        runtime.Gosched()
    }
    return 0
}

Runtime: 44 ms, faster than 5.84% of Go online submissions for Majority Element.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Majority Element.

• map的定义，是make(map[int]int)，一开始把struct当成map写了😂

• 判断某元素是否存在，感觉这个if _, ok:=..的模板很好用

• map的for遍历，返回的俩数就是key和value。如果是slice或array，是index和element。

排序

想到排序来化简算法，不过想的也是计算出现最多次数的数字。

其实排序后，只要看一下n/2的数字是哪个，那就是众数了。

var majorityElement = function (nums) {
  nums.sort()
  if (nums.length % 2 === 0) {
    return nums[Math.ceil(nums.length / 2)]
  } else {
    return nums[Math.floor(nums.length / 2)]
  }
};

Runtime: 80 ms, faster than 20.69% of JavaScript online submissions for Majority Element.

Memory Usage: 37.4 MB, less than 64.29% of JavaScript online submissions for Majority Element.

func majorityElement(nums []int) int {
    sort.Ints(nums)
    return nums[len(nums)/2]
}

Runtime: 16 ms, faster than 92.69% of Go online submissions forMajority Element.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Majority Element.

go很神奇，直接len(nums)/2，都不需要判断奇偶的，就能有正确结果。。

开心消消乐

作者：linxinfu

链接：https://leetcode-cn.com/problems/two-sum/solution/shi-yong-zhan-lai-ji-yi-by-linxinfu/

看到评论取的这个名字，几乎要被笑死😂

做一个栈，如果和栈顶元素一样，就入栈，不一样就出栈。感觉更像是反向的消消乐

换我一百年都想不到这种骚操作😂😂

var majorityElement = function (nums) {
  let stack = []
  for (const num of nums) {
    if (!stack.length) {
      stack.push(num)
    } else {
      const top = stack.pop()
      if (top === num) {
        stack.push(top)
        stack.push(num)
      }
    }
  }
  return stack.pop()
};

Runtime: 48 ms, faster than 99.71% of JavaScript online submissions for Majority Element.

Memory Usage: 38.3 MB, less than 7.14% of JavaScript online submissions for Majority Element.

go如何制作栈的参考

go里面似乎没有现成的栈，只能用切片，然后手写相关的操作。

func majorityElement(nums []int) int {
    var stack []int
    for _, elem := range nums {
        if len(stack) == 0 {
            stack = append(stack, elem)
        } else {
            top := stack[len(stack)-1]
            stack = stack[0 : len(stack)-1]
            if top == elem {
                stack = append(stack, top, elem)
            }
        }
        runtime.Gosched()
    }
    return stack[len(stack)-1]
}

Runtime: 28 ms, faster than 18.02% of Go online submissions forMajority Element.

Memory Usage: 6.2 MB, less than 50.00% of Go online submissions forMajority Element.

空切片，似乎只能用var stack []int来定义，tack := []int{}这样goland似乎不推荐。

好像还是用原生的api速度更快，手写的api始终比不上亲生的。。

Boyer-Moore 投票算法

听这名字就感觉很厉害，其实和消消乐差不多。

两个的原理是一样的：众数比其他所有数，都要多。

因此，消消乐是把相同的留下，不同的pop，留下的必然是众数。

这个投票算法，是随机定一个数是众数，同样的就+1，不同的就-1。如果为0，那么定下一个数为众数。

var majorityElement = function (nums) {
  let ans = nums[0]
  count = 1
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      ans = nums[i]
      count++
      continue
    }
    if (nums[i] === ans) {
      count++
    } else {
      count--
    }
  }
  return ans
};

Runtime: 60 ms, faster than 81.84% of JavaScript online submissions for Majority Element.

Memory Usage: 37.3 MB, less than 71.43% of JavaScript online submissions for Majority Element.

func majorityElement(nums []int) int {
    var (
        count int
        ans   int
    )
    for _, elem := range nums {
        if count == 0 {
            ans = elem
            count = 1
            continue
        }
        if elem == ans {
            count++
        } else {
            count--
        }
        runtime.Gosched()
    }
    return ans
}

Runtime: 24 ms, faster than 25.49% of Go online submissions forMajority Element.

Memory Usage: 5.9 MB, less than 50.00% of Go online submissions forMajority Element.

消消乐和算法相比，是拿空间换时间了。不过我更喜欢消消乐的容易理解。

随机

看到了官网的随机解法，没看懂。不过其思想是：众数出现的概率更大

我就想，能不能和消消乐结合一下，随机挑数进栈，玩消消乐。只要最后答案出错的概率很小，那就可以接受不是吗。大不了roll两次，一样了再给答案，不一样再roll一次取一样的值。

那么应该随机多少次呢？首先想到的就是n/2次，也没仔细算过，就觉得本该如此😂

测试环境

发一下抽风的js测试环境。。不知道为啥ans===target也不让过。。

// ======= init ==========
const wrongMsg = (ans, target, index) => {
  console.log("😶 wrong:", index);
  console.log("* target: ", target);
  console.log("* ans: ", ans);
};

const TreeNode = function (val) {
  this.val = val;
  this.left = this.right = null;
};

function ListNode(val) {
  this.val = val;
  this.next = null;
}

// ======= code ==========
// =======================
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let ans = nums[0]
  count = 1
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      ans = nums[i]
      count++
      continue
    }
    if (nums[i] === ans) {
      count++
    } else {
      count--
    }
  }
  return ans
};

// ======== 测试 ==========
const TEST_DATA = [
  // {
  //   inputs: [3, 2, 3],
  //   target: 3
  // },
  // {
  //   inputs: [2, 2, 1, 1, 1, 2, 2],
  //   target: 2
  // },
  // {
  //   inputs: [1],
  //   target: 1
  // },
  // {
  //   inputs: [2, 2],
  //   target: 2
  // },
  {
    inputs: [6, 5, 5],
    target: 5
  },
];

var __main = () => {
  for (let i = 0; i < TEST_DATA.length; i++) {
    const test = TEST_DATA[i];
    // == func ==
    const ans = majorityElement(test.inputs)
    // ==========
    const target = test.target
    if (ensure(ans, target, i)) {
      return
    }
  }
  console.log("✅✅ all right")
}

const ensure = (ans, target, index) => {
  const Ans = (JSON.stringifyans)
  const Target = JSON.stringify(target)
  if (Ans !== Target) {
    wrongMsg(ans, target, index + 1);
    return true
  }
  return false
};

// ==== 主函数 ======
__main()

不同以往用web worker来防止死循环，其实只要用node在本地跑，死循环了就ctrl+c退出就完事了，就没那么复杂了。