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

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

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

示例.png

分析: 题中提到数组中有一个数字出现的次数超过数组长度的一半, 重点是有 真的存在不可能不存在这样的元素明白吗 ?

思路一: 对数组进行排序, 排序后如果肯定有出现次数超过一半的那么肯定在中间

  时间复杂度: O(nlogn)
  空间复杂度: O(nlogn)
 class Solution {

    public int majorityElement(int[] nums) {

        //0.边界判断
        if(nums==null||nums.length==0) return -1;

        //1.题意是数组中有次数超过一半的数字 让找出来
        Arrays.sort(nums);

        //2.题意是数组中有次数超过一半的数字 让找出来, 脑筋急转弯如果有倒推中间的数字肯定就是这个数字了
        return nums[nums.length>>1];

    }

}

思路1提交结果.png

思路二 : 用哈希表来计数: key: 元素值 val: 元素出现的次数, 一趟循环即可找到这样元素 (此思路是通用方式: 不管有没有要寻找的元素 只要有就能找到)

  时间复杂度: O(n)
  空间复杂度: O(n)

class Solution {
    public int majorityElement(int[] nums) {

        //0.边界判断
        if(nums==null||nums.length==0) return -1;

        //1.定义需要的数据结构
        Map<Integer,Integer> map = new HashMap();

        //2.遍历
        for(int i = 0;i < nums.length;i++) {

            //key:nums[i] val:出现次数
            int count = (map.containsKey(nums[i]))?(map.get(nums[i])+1):1;

            //更新元素出现的次数
            map.put(nums[i],count);

            //找到合适的元素
            if(map.get(nums[i]) > (nums.length>>1)) return nums[I];

        }

        return -1;

    }
}

思路2提交结果.png