169. 多数元素

1. 题目描述

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

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

示例 1:

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

示例 2:

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

2. 解题思路

对于这道题目，最直接的办法就是将数组中的元素以及其次数保存早map中，然后遍历数组，找出大于次数大于边界值的元素。

该方法的时间复杂度为O(n)，空间复杂度为O(n)。

还可以使用双指针求解，具体实现思路如下：

• 首先将数组进行排序
• 之后定义两个指针i和j，i在左，j在右。首先i不动，j不断向右移动，直到和i对应的元素不相同时停止
• 若此时满足j - i大于边界值，就返回结果，如果小于边界值，就将i移动到j的位置，继续向右移动j，重复上一步

• 如果j已经到最后一个元素，就返回此时的i对应的值

  3. 代码实现

  /**
  * @param {number[]} nums
  * @return {number}
  */
  var majorityElement = function(nums) {
    let number = 0
    const map = {}
    if(nums.length){
        // 求出中间值
        const bound = Math.floor(nums.length / 2)
        // 将每个元素及次数保存在map中
        nums.map((num) => {
            map[num] = map[num] ? map[num] + 1 : 1
        })
        // 遍历数组
        Object.keys(map).map((key) => {
            if(map[key] > bound){
                number = key
            }
        })
    }
    return number
  };

  双指针：

  /**
  * @param {number[]} nums
  * @return {number}
  */
  var majorityElement = function(nums) {
    let number = 0
    nums.sort()
    number = nums[0]
    if(nums.length > 1){
        const bound = Math.floor(nums.length / 2)
        for(let i = 0, j = 1; j < nums.length; j++){
            if(nums[i] !== nums[j]){
                if(j - i > bound){
                    number = nums[i]
                }else{
                    i = j
                }
            }
            if(j === nums.length -1){
                number = nums[i]
            }
        }
    }
    return number
  };

  4. 提交结果