LeetCode-169.Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

使用排序，输出索引为nums.length/2的值，时间复杂度O(nlogn)；

使用分治的思想，不断递归左半部分最常出现的值和右半部分最常出现的值，如果两个值不一样，需要获取两个值的个数并判断，时间复杂度为O(nlogn)；

使用map，时间复杂度O(n)，空间复杂度O(n)

public int majorityElement(int[] nums) {//map my
        Map<Integer,Integer> counts = new HashMap<>();
        for (int i = 0; i < nums.length ; i++) {
            if(counts.containsKey(nums[i])){
                counts.put(nums[i],counts.get(nums[i])+1);
            }
            else{
                counts.put(nums[i],1);
            }
        }
        int re =0;
        int max =-1;
        for (Map.Entry<Integer,Integer> entry: counts.entrySet()) {
            if(-1==max||entry.getValue()>max){
                re = entry.getKey();
                max= entry.getValue();
            }
        }
        return  re;
    }

利用多于一半的特性，时间复杂度O(n)，空间复杂度O(1)

public int majorityElement(int[] nums) {//my
        int re = 0;
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            if(0==num){
                re = nums[i];
                num++;
            }
            else{
                if(nums[i]==re){
                    num++;
                }
                else{
                    num--;
                }
            }
        }
        return  re;
    }

剑指offer中出现次数超过数组一半的数字不总存在，得到最后的结果，并判断其存在的

 1 public int MoreThanHalfNum_Solution(int [] array) {//my
 2         int result = 0;
 3         int count =0;
 4         int len = array.length;
 5         for (int i = 0; i < array.length; i++) {
 6             if(0 ==count ){
 7                 result = array[i];
 8             }
 9             if(array[i]!= result){
10                 count --;
11             }
12             else{
13                 count++;
14             }
15         }
16         count = 0;
17         for (int i = 0; i < array.length; i++) {
18             if(array[i] == result){
19                 count ++;
20             }
21         }
22         if(count<=(len/2)){
23             result =0;
24         }
25         return result;
26     }