求star

题目#

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

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length

• 1 <= n <= 5 * 104

• -109 <= nums[i] <= 109

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

解题:tada:#

①摩尔投票法#

TIP

​ 摩尔投票法,先假设第一个数过半数并设cnt=1；遍历后面的数如果相同则cnt+1，不同则减一，当cnt为0时则更换新的数字为候选数（成立前提：有出现次数大于n/2的数存在）

​ 假设几个国家之间发生混战，最后还有人活下来的国家就胜利，而你方人口超过总数的一半，并且保证每个人都能一对一同归于尽，那么最差的情况也就是所有人都联合起来对付你，但只要不内斗，最后一定是你赢，核心就是 对拼消耗

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
   let count = 1;
   let res = nums[0]
   for(const num of nums){
       if(num != res){
           count--;
           if(count == 0 ){
               count = 1;
               res = num
           }
       }else {
           count++;
       }
   }
   return res;
};

②哈希表(HashMap)#

TIP

​ 用hashmap来存储数据，键代表一个元素，值代表这个元素出现的次数,然后只需要遍历一遍即可

C++#

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> count;
        int maj=0,cnt=0;
        for(int num : nums){
            ++count[num];
            if(count[num]>cnt){
                maj = num;
                cnt = count[num];
            }
        }
        return maj;
    }
};

③先排序#

TIP

​ 这个题目有一个重要的前提，那就是这个多数元素出现的次数大于[n/2]，所以可以直接排序，然后输出最中间的值

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let newNums = nums.sort((a,b)=> a-b)
    let len = Math.floor(nums.length/2);
    return newNums[len]
};