Array 面试题 17.10. 主要元素众数

2020-10-15

思路

先求出数组的一般长度是n（向下取整）
遍历数组，元素出现次数 count > n,,则为重要元素。
- 定义一个对象，元素名是数字，元素值是出现的次数（hashMap），每次循环比较 count（通过 map.getOrDefault(要查找的元素, 默认返回值)方法）和 n
- 投票算法

首先需要明确的是：主要元素要么有一个要么一个也没有。

优化：数组只有一个元素，数组为空

方法一：暴力破解

计算数组一般的长度 len
双层顺序循环，依次统计每个元素出现的次数 count ，在外层循环比较 count 和 len
找到唯一值 count > len ,就找到主要数，返回主要输退出循环，循环结束还没有找到，就返回 -1

public int majorityElement(int[] nums) {
       if (nums.length == 0) return -1;
       if(nums.length == 1) return nums[0];
       // 暴力破解法
       int len = nums.length / 2;
       for(int num : nums){
           int  count =0;
           // 依次比较 num 重复了多少次
           for(int ele : nums){
               if(ele == num){
                   count++;
               }
           }
           // 如果 num 重复次数超过一半 ，则为主要数，返回num，否则结束循环返回 -1
           if(count > len) return num;
       }
       return -1;
   }

复杂度分析

时间复杂度：O(n2)

暴力解法包含两重嵌套的 for 循环，每一层 n 次迭代，因此时间复杂度为 O(n2) 。

空间复杂度：O(1)

暴力解法没有分配任何与输入规模成比例的额外的空间，因此空间复杂度为 O(1)。

方法二：哈希表

这个问题可以视为查找问题，对于查找问题往往可以使用时间复杂度为 O(1) 的 哈希表，通过以空间换时间的方式进行优化。

定义maxNum 和 maxCount 和一个哈希表，哈希表的键是数字，值是数字出现的次数
遍历 nums 数组，计算元素（num）出现的次数 count，将这个(num,count) 加入 hasmap（键不能重复，但是值是最新的元素）
每次遍历中，比较 maxCount 和 count ，更新 maxCount 值 maxNum

// 哈希表
Map<Integer,Integer> map = new HashMap<>();
int maxNum = 0, maxCount = 0;
for(int num : nums){
    int count = map.getOrDefault(num,0) + 1;
    // 更新 map 元素
    map.put(num, count);
    // 更新 maxNum 和 maxCount
    /*if(count > maxCount){
        maxCount = count;
        maxNum = num;
    }*/
    if(count > len) return num;
   // if(maxCount > len) return maxNum;
}
return -1;

不需要 maxNum 和 maxCount，在每次循环的时候，比较当前元素出现的次数 count 和 len 即可，设置 maxNum 和 maxCount 适合找出众数而不是主要数

复杂度分析
时间复杂度：O(n)

总共有一个循环，里面哈希表的插入是常数时间的，因此时间复杂度为 O(n)。

空间复杂度：O(n)

哈希表占用了额外的空间 O(n)，因此空间复杂度为 O(n)。

方法三：摩尔投票法

寻找数组中超过一半的数字，这意味着数组中其他数字出现次数的总和都是比不上这个数字出现的次数 。即如果把该众数记为 +1 ，把其他数记为 −1 ，将它们全部加起来，和是大于 0 的。

设置两个变量 candidate 和 count ，candidate 用来保存数组中遍历到的某个数字（初始化为第一个元素），count 表示当前数字的出现次数（初始化为 1）
遍历数组
- 遍历的元素 = candidate ，count + 1
- 遍历的元素 != candidate ，count -1
- count = 0 的时候（只有 count ！= 0 的时候，才是主要数），更新 candidate 为当前元素，count 也重置为 1
candidate 不一定就是主要数，但一定是众数，此时计算 candidate 出现的次数，和 len 比较，确定是否为主要数。

// 摩尔投票法
    int candidate = nums[0],count=1;
    // 遍历数组
    for(int  i = 1;i < nums.length; i++){
        // count == 0 更新 candidate 的值为当前元素
        if(count ==0){
            candidate = nums[i];
            count = 1  ;
        }else if(nums[i] == candidate) count++;
                 else count--;
    }

    // 只是找到了众数，不一定是主要数，遍历数组找到众数的个数，再次判断
    int len = nums.length /2 ;
    count = 0;
    for(int num : nums){
        if(num == candidate) count++;
        if(count  > len ) return candidate;
    }
    return -1;
    }

复杂度分析

时间复杂度：O(n)

总共只有一个循环，因此时间复杂度为 O(n)。

空间复杂度：O(1)

只需要常数级别的额外空间，因此空间复杂度为 O(1)。

思路

方法一 ：暴力破解

方法二 ：哈希表

方法三：摩尔投票法

方法一：暴力破解

方法二：哈希表