39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出：2

限制：1 <= 数组长度 <= 50000

摩尔投票

1. 无需开辟额外空间 ```javascript /**
   • @param {number[]} nums
   • @return {number} */ var majorityElement = function (nums) { let ans = 0, count = 0; for (let i = 0; i < nums.length; i++) { // 当前没有领先的 // 那么当前遍历到的数就作为领先的 if (count === 0) { ans = nums[i]; count++; } else { // 相同的票就加一 // 不相同的票就抵消 count += nums[i] === ans ? 1 : -1; } } return ans; };

<a name="NFGu5"></a>
## 哈希遍历
1. 求出一半长度 巧用位运算 **`max = nums.length >> 1`**
1. 构造哈希表 
1. 遍历构造hash 过程中当 `**hash[num] > max**` 退出循环 直接返回期望值 return num
```javascript
var majorityElement = function (nums) {
  const max = nums.length >> 1,
    hash = {}
  for (const num of nums) {
    hash[num] ? hash[num]++ : hash[num] = 1
    if (hash[num] > max) return num
  }
};