Leetcode169.多数元素

1.题目描述

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

2.解法

1.使用HashMap

class Solution {
    public int majorityElement(int[] nums) {
        return countNum(nums).getKey();
    }
    public Map.Entry<Integer,Integer> countNum(int[] nums){
        //使用Hash Map存储每个元素即出现的次数
        Map<Integer,Integer> counts = new HashMap();
        for(int i : nums){
            if(!counts.containsKey(i))
                counts.put(i,1);
            else{
                counts.put(i,counts.get(i)+1);
            }
        }
        //遍历整个HashMap,找出出现次数最多的
        Map.Entry<Integer,Integer> hashEntry = null;
        for(Map.Entry<Integer,Integer> entry : counts.entrySet()){
            if(entry == null || entry.getValue() > nums.length/2)
                hashEntry = entry;
        }
        return hashEntry;
    }
}

首先将给定数组nums以<数组中元素,元素出现的次数>的键值对形式加入到HashMap中,如果已经存在对应的key,那么取出key的值,进行加1操作,然后再写入到HashMap中进行覆盖,如果没有对应的key,直接put键值对<数组中元素,1>即可。最后对整个HashMap进行遍历,找出value大于 ⌊ n/2 ⌋ 的entry,然后取出entry的key即可。

这种方法使用了Java的api,既然是做算题,按照道理来讲是有一些耍赖的,本来想的是使用Set集合也可以解决这个问题的。

2.排序

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

image

这种方法利用了多数元素大小总是大于数组长度一半的特点,将数组进行排序后,即使多数元素为极端元素,

如果数组长度为奇数(7):

这时如果多数元素为最小值,为数组下面的红线,如果为最大值,为数组上面的红线,也就是在nums[length / 2]的位置,不管多数元素是多少,一定会路过这里的,既然极端元素都可以路过这里,那么普通元素更可以路过这里了,只要路过这里,nums[length/2]这里返回的元素就是多数元素

如果数组长度为偶数(6):

同上面一样,在nums[length/2]也总是可以返回多数元素


总是觉得这个方法既有取巧的地方,又有一些耍赖,既然是算法题目,居然直接调用了Arrays.sort()方法,而且这种解体思路有经验的成分。

3.随机化方法

class Solution {
    public int randRange(Random rand,int min,int max){
        return rand.nextInt(max-min) + min;
    }
    public int countOccurence(int[] nums,int num){
        int count = 0;
        for(int i : nums){
            if(i == num)
                count++;
        }
        return count;
    }
    public int majorityElement(int[] nums) {
       Random rand = new Random();
       while(true){
           int candidate = nums[randRange(rand,0,nums.length)];
           if(countOccurence(nums,candidate) > nums.length/2)
                return candidate;
       }
    }
}

因为多数元素的数量是大于[length/2]的,所以这时随机从数组中选出一个元素,并统计其出现次数,它是多数元素的概率是非常大的

我们也可以从nums数组的第一个元素,逐一统计各个元素出现的次数,这样确实可行,但是既然多数元素的占比这么大,应该还是随机化的方法更快一些。

4.分治法

class Solution {
    public int majorityElement(int[] nums) {
       return majorityElementRec(nums,0,nums.length-1);
    }
    public int countInRange(int[] nums,int num,int lo,int hi){
        int count = 0;
        for(int i = lo;i <= hi;i++){
            if(nums[i] == num)
                count++;
        }
        return count;
    }
    public int majorityElementRec(int[] nums,int lo,int hi){
        //如果数组只剩一个元素,直接返回
        if(lo == hi)    return nums[lo];
        //分别获得分治后两边数组的多数元素
        int mid = lo + (hi - lo) / 2;
        int left = majorityElementRec(nums,lo,mid);
        int right = majorityElementRec(nums,mid+1,hi);
        //如果相等,直接返回
        if(left == right)   return left;
        //不相等,进行全局的次数比较
        int leftCount = countInRange(nums,left,lo,hi);
        int rightCount = countInRange(nums,right,lo,hi);
        return leftCount > rightCount ? left:right;
    }
}

思路:

如果数 a 是数组 nums 的众数,如果我们将 nums 分成两部分,那么 a 必定是至少一部分的众数。

我们可以使用反证法来证明这个结论。假设 a 既不是左半部分的众数,也不是右半部分的众数,那么 a 出现的次数少于 l / 2 + r / 2 次,其中 l 和 r 分别是左半部分和右半部分的长度。由于 l / 2 + r / 2 <= (l + r) / 2,说明 a 也不是数组 nums 的众数,因此出现了矛盾。所以这个结论是正确的。

这样以来,我们就可以使用分治法解决这个问题:将数组分成左右两部分,分别求出左半部分的众数 a1 以及右半部分的众数 a2,随后在 a1 和 a2 中选出正确的众数。


我们使用经典的分治算法递归求解,直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数,直接返回即可。如果回溯后某区间的长度大于 1,我们必须将左右子区间的值合并。如果它们的众数相同,那么显然这一段区间的众数是它们相同的值。否则,我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

5.摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

这个算法还是比较抽象的,虽然能够在这个题目里面进行理解,但是在其他题目中能够驾驭起来还是非常难的,假如现在的nums数组中元素为[3,3,3,2,2,2,2],那么就可以理解为一个投票机制,只有一个元素的票数count在经过一轮投票之后还大于0,才能作为候选人candidate,因为题目中所说一定存在多数元素,那么就不存在鱼死网破,没有一个元素是多数元素的情况,首先从数组的第一个元素开始,如果count为0,那么随便选择第一个元素作为候选者,接下来数组的元素中, 如果和candidate相同,那么count++,如果不相同,出现异己力量,那么count--,进行一轮之后,因为题目规定,多数元素总是大于数组长度的一半,所以最终count>0的元素返回