[LeetCode] NO. 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.

 

[题目解析] 根据题目需要求数组中，出现次数过半的元素。最容易想到的就是直接的去遍历数组计数，然后出现次数过半的即为所求。

 public int majorityElement(int[] nums) {
       int result = 0;
       HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
       for(int i = 0; i < nums.length; i++){
           int num = nums[i];
           if(map.containsKey(num)){
               map.put(num, map.get(num) + 1);
           }else{
               map.put(num,1);
           }
           f(map.get(num) > (nums.length)/2){
               result = num;
           }
       }
       return result;
  }

还有没有其他方法呢？比较容易能想到，如果是一个有序数组，那么中间位置的数一定就是所求。我们可以对数组进行排序。

    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

这里用到了排序，其实我们如果求第(n/2)+1小的数，也是可以的。问题就转化成，求第i小的数。

        求第i小的数，可以根据快速排序的思想。快速排序是找一个数作为基准数，一次遍历后令该基准数处于最终排序后的位置，即比它小的数都在左边，大的都在右边。我们可以根据这一思想，随机取一个数，根据该方法求得最终位置后，若该位置即为i，则直接返回。若该位置比i大，则要求的数在i的左边的数组中，转化为子问题。若该位置比i小，则问题转化成求i右边的数组的第i-s小的数(s是该位置左边的元素个数)。最终可求得结果。

        此外，有一种比较巧妙的方法来解决该问题：摩尔投票算法。

        基本思想: 遍历数组，每次删除一对不同的数，则最后剩下的元素即为所求。

        

  public int majorityElement(int[] nums) {
        int ret = 0; 
        int count = 0;
        for(int num : nums){
            if(count == 0){
                ret = num;
            }
            if(ret == num){
                count++;
            }else{
                count--;
            }
        }
        return ret;
    }