算法练习- LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字

今日心情：生活在慢慢走上正轨，慢慢走总能达到想去的地方。

题目描述：

LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

 

---

解题代码 1：（看的题解思路：投票法 时间复杂度O（n）+ 空间复杂度O（1））

class Solution {
    public int majorityElement(int[] nums) {
        int vote = 0;
        int x = 0;
 
        for(int num : nums){
            if(vote == 0){
                x = num;
            }
            vote += (num == x) ? 1 : -1;
        }
       return x;
    }
}

解题代码 2：（自己想的思路：HasMap统计 时间复杂度O（n）+ 空间复杂度O（n））

class Solution {
    public int majorityElement(int[] nums) {
 
        int half = nums.length/2;
        HashMap<Integer,Integer> map = new HashMap<>();
 
        for(int num: nums){
            if(!map.containsKey(num)){
                map.put(num,1);
            }else{
                map.put(num,map.get(num)+1);
            }
        }
 
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() > half){
                return entry.getKey();
            }
        }
        return -1;
    }
}

---

解题思路1：

题解方法主要利用了题目中可以假设数组是非空的，并且给定的数组总是存在多数元素。所以一定存在这样的数，其出现次数超过数组半数。

（1）可以判断如果当前投票数为 0 ， 则将当前值保存起来，与下一个值进行比较，如果当前值与下一个值相等，则投票加1，否则投票-1；

（2）然后当投票为0的时候就更新比较值；

（3）遍历完成后投票值一定大于0，此时的保存的值就是出现次数超过数组半数的数。

主要就是利用了该数出现次数一定是大于半数数组长度的特性。

---

解题思路2：

自己首先拿到题想到的就是使用HashMap进行统计，然后找到出现次数超过数组半数的值，操作时间复杂度为O（n）， 空间复杂度为O（n）。看题解使用的投票方法可以将空间复杂度优化到  O（1）。

（1）遍历数组，将所有数存入HashMap中，如果当前数不存在于HashMap，当前数作为key，值为1，如果当前数已经存在于HashMap中，则更新以当前数为key的值，获取以当前数为key的值然后加1进行更新；

（2）遍历map，获取值大于半数数组长度的key；

（3）返回找到的key值。

---