14-169 多数元素(类似于求众数)

题目描述：

解题思路：

1. 可以使用HashMap

   • 对于数组中的每一个元素，依次加入到HashMap中去
   • 在每次加入前，检查该map中是否含有此关键字
     • 如果没有则将该值设为1
     • 如果已经存在该关键字，则get(key)+1
   • 然后循环遍历给map，记录key的value最大值的那个entry，然后返回该key
   • 由于HashMap的查找和存储只需要常数的时间，因此该方法的时间复杂度是O(n)，期间使用了HashMap，开辟了一个O(n)的空间。

2. 可以将该数组进行排序，排序完成之后，由于有至少n/2的数字才称之为该众数，因此无论奇偶，索引值为n/2的这个值，即是众数。

   • 排序需要的时间复杂度是O(nlogn)
   • 空间复杂度，使用了java自带的排序算法，需要O(log n)的栈空间

3. 分治法

   如果数a是数组nums的众数，现在将nums分成两部分，那么a至少是其中一部分的众数。

   • 因此，将数组分成左右两部分，分别求出左半部分的众数al，和右半部分的众数ar；
   • 然后在al和ar中选取正确的众数

4. 摩尔投票法

   如果把众数即为+1；把其他数记为-1；显然和大于0

   • 我们维护一个候选众数candidate和它出现的次数count。初始时，candidate可以为任意的数，count为0
   • 遍历数组中的所有元素，对于每个元素x进行判断，在判断和candidate之前，先判断此时的count是否为0；
     • 如果为0，说明candidate需要更换了
     • 此时需要将x的值赋值给candidate
   • 判断x；
     • 如果x与candidate相等，count++
     • 反之，count--
   • 时间复杂度O(n)；空间复杂度O(1)

代码：

//哈希表
class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int count = 0;
        for(int i = 0;i < nums.length;i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i])+1);
            }
        }
        Map.Entry<Integer,Integer> majorityEntry = null;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(majorityEntry == null || entry.getValue() > majorityEntry.getValue() ){
                majorityEntry = entry;
            }
        }
        return majorityEntry.getKey();
    }
}

//排序
class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len/2];
    }
}

//分治
class Solution {
    public int countMajority(int left,int right,int[] nums,int key){
        int count = 0;
        for(int i = left;i <= right;i++){
            if(nums[i] == key){
                count++;
            }
        }
        return count;
    }

    public int divide(int left,int right,int[] nums){
        if(left == right){
            return nums[left];
        }
        int mid = (left + right) >> 1;
        //int mid = (right-left) / 2 + left;
        int al = divide(left,mid,nums);
        int ar = divide(mid+1,right,nums);
        if(al == ar){
            return al;
        }
        int leftCount = countMajority(left,right,nums,al);
        int rightCount = countMajority(left,right,nums,ar);
        return leftCount > rightCount ? al : ar;
    }

    public int majorityElement(int[] nums) {
        return divide(0,nums.length-1,nums);
    }
}

//摩尔投票法
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int majority = nums[0];
        for(int i = 0;i < nums.length;i++){
            if(count == 0){
                majority = nums[i];
                count++;
            }else{
                if(majority == nums[i]){
                    count++;
                }else{
                    count--;
                }
            }
        }
        return majority;
    }
}

14-169 多数元素(类似于求众数)

原文：https://www.cnblogs.com/forrestyu/p/14758067.html