心得体会

这个题目有两个版本Majority Element,和Majority Element II,解题的方法比较巧妙,有点想不到的感觉,并且证明过程也很有趣,所以就记录下来(具体详情见正文题解)。

题解正文

题目描述算法分析与设计第五次作业(leetcode 中 Majority Element 题解)-LMLPHP算法分析与设计第五次作业(leetcode 中 Majority Element 题解)-LMLPHP

问题分析

题目要求majority number,也就是出现次数最多的数,第一个题目求占比超过1/2的数,第二题要求占比超过1/3的那些数,其实这种题目可以拓展为求占比超过1/k的那些数字。下面会从简单版本I的求解过渡到版本II,最后得出1/n众数的求解。

解题思路

下面的思路中,nums表示输入的数字数组

  1. 最简单的方法当然是对于每一个数字都用一个num记录数值,一个count记录出现次数,最后筛选count大于nums.size()/k的那些数字。这样做的话时间复杂度和空间复杂度都是线性的,达不到题目要求的O(1)空间复杂度。
  2. 所以换一个思路,我们把考虑把数字进行配对,比如求出1/2众数,因为占比超过1/2的数字最多有一个,所以我们可以将1/2众数和其它数字两两配对,如果存在1/2众数,那么配对到最后一定还会有1/2众数剩余,因为1/2众数占比超过1/2,也就比其它数字个数总和还多。配对完成之后,还剩下那些没法配对的数字,这些数字就是1/2众数了。所以换一个思路,我们把考虑把数字进行配对,比如求出1/2众数,因为占比超过1/2的数字最多有一个,所以我们可以将1/2众数和其它数字两两配对,如果存在1/2众数,那么配对到最后一定还会有1/2众数剩余,因为1/2众数占比超过1/2,也就比其它数字个数总和还多。配对完成之后,还剩下那些没法配对的数字,这些数字就是1/2众数了。
    通过上面的分析我们将这个问题转化成了一个配对问题,但是具体怎么配对呢:可以用一个num记录数值,count记录对应数值已经出现的次数(初值为0),然后对nums数组遍历,如果遇到和当前num记录数值相同的数,就将count递增,这样做的含义是加入配对队列,等待其它的数字与之配对相消;反之和num值不同则需要将count递减(要求count>0),这样做对应的含义是将两个不同类别的数字配对相消;如果count值为零就将num值替换为遍历的当前数字nums[i] 并递增count。这样做到最后nums数组中数字只有两个结果:a.通过配对消除;b.加入待配对队列(也就是num&count表示的单个数字组成的队列),根据上面的分析,被存在num中的只能是1/2众数,少数数字和部分1/2众数被配对消除。
    问题解决,但是细节部分还有一些问题:
    • 加入到配对队列的不一定就是1/2众数,也可能是1/2众数之外的数字,但是这不影响算法的正确性:
      首先我们确认,加入到配对队列的数字只有两种,1/2众数和其它数字。
      如果加入配对队列的是1/2众数那么就是上面分析的情况,不会有问题。
      如果加入到配对队列的不是1/2众数,那么后续遍历到的与之不同的数字也有两种可能,一种可能是1/2众数,另一种可能是其它数字,如果是1/2众数,那么和上面分析的情况是一样的,即1/2众数 vs 其它数字配对相消;如果不是1/2众数,那么就是其它数字 vs 其它数字配对相消,这样对于找出1/2众数更加有利,因为其他数字正在以比1/2众数更快的速度被配对消去,又因为其他数字本来就比1/2众数少,那么自然更快被消去。
      所以无论如何,一个1/2众数至少消去一个其他数字,最后留在等待配对队列中的只能是1/2众数(因为其它的数都被消去了)。
    • 万一1/2众数根本不存在,这个可以在上述算法做完之后,遍历一遍nums数组求出num数值出现次数,超过n/2则存在,并且就是num,反正不存在1/2众数,因为1/2众数必然满足前面分析到的情况。
  3. 扩展到求1/k众数,思路和求1/2众数一样,只不过上次是每组两个数字配对,这次是每组k个数字的配对。
    具体做法:将众数与非众数划分为k个一组(其中众数每一个只出现一次,其它数字用非众数填充),就能够在第nums.size()/k次消去之前将所有非众数全部去掉,而余下的数字都是1/k众数。
    为什么是这样,可以如下证明:假设有x(0<=x<1)个1/k众数,首先创建一个大小nums.size()的容器N,我们将N均分为k个小容器,其中x个小容器用来放1/k众数,每一个小容器放入不同的1/k众数,这样这x个小容器必定被装满而且每个1/k众数还有剩余;与此同时,均分剩余的非1/k众数填充剩下的容器,一定装不满(因为所有数字加起来刚好填满所有小容器,现在有一些1/k众数还在外面,所以剩余的k-x个小容器一定装不满)。然后我们每次从每个容器中去掉一个数字,对应的实际含义是将k个不同类别的数字配对相消,这样在第nums.size()/k次消去之前所有的小容器都将清空,留下的x个容器中全都是1/k众数,证毕。
    最后说一下配对怎么做(其实和前面1/2众数配对差不多):申请两个大小为k-1的数组num[k-1]={}和count[k-1]={}用来记录众数值和个数,然后遍历nums,如果在num数组中有某个数字与当前的nums[i]相等,相应的count[i]递增,这样做的含义是将数字加入配对队列,等待其它的数字与之配对相消;反之如果在num数组中不存在这样的数字,则需要将所有count[i]递减(要求count数组中所有count>0),这样做对应的含义是将k个不同类别的数字配对相消;如果count数组中存在某个count[i]值为零,就将对应的num[i]值替换为遍历的当前数字nums[i] 并递增count。这样做以后所有可能的1/k众数都在num数组中了,我们只需再遍历一次nums数组求出num[i]对应count[i],如果count[i]>nums.size()/k那么num[i]就是1/k众数。
    如果你还想要问“加入到配对队列的不一定就是1/k众数,也可能是1/k众数之外的数字怎么办”这样的问题,那我的回答和前面2.1说到的一样,不会影响结果,因为这样的话非众数将以更快的速度被消去,更利于求出答案。

算法步骤

因为1/2众数求解、1/3众数求解都可以归入1/k众数求解,下面只给出1/k众数求解的步骤:
下面的nums数组为输入的带查询数组,num,count都是大小为k的数组,用于存储k-1个可能的众数。

  1. 遍历nums数组,对于每个nums[i]
    1. 遍历num数组,对于每个num[j]
      判断nums[i]是否等于num[j],如果是,递增count[j],并跳出当层循环(break),并在出循环后跳过外层循环余下代码(continue);
    2. 遍历count数组,对于每个count[j]
      是否存在某个count[j]等于0,如果是,将num[j]设置为当前遍历到的数字nums[i],并设置count[j]为1,然后跳出当层循环(break),出循环之后跳过外层循环余下代码;
    3. 遍历count数组将所有count[j]递减;
  2. count数组全置为零;
  3. 遍历nums数组,对于每个nums[i]. 遍历nums数组,对于每个nums[i]
    1. 遍历遍历num数组,对于每个num[j]
      如果nums[i]和num[j]相等就将count[j]递增;
  4. 遍历count数组,对每个count[i]
    如果count[j]>nums.size()/k就输出num[i]作为结果之一;

算法复杂度分析

时间复杂度:只需要一次遍历nums数组求出k个可能的1/k众数(这其中每次循环都要遍历两个大小为k的数组num和count,判断num[i]是否等于当前数字,count是否等于0);再一次遍历求出k个数字对应的个数count(这其中每次循环都要遍历num数组判断num[i]是否等于当前数字);最后一次遍历num数组判断数字是否确实是众数;所以总的空间复杂度为O(2kn)+O(kn)+O(k)=O(kn)。如果k是常数级别,复杂度可写为O(n)。
空间复杂度:一共使用两个大小为k的数组num和count,空间复杂度为O(k),如果k为常数级别,可写为O(1)。

代码实现&结果分析

  • 1/2众数求解:
    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int num = 0;
            int count = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if ( num == nums[i] ) {
                    count++;
                } else if ( count == 0 ) {
                    num = nums[i];
                    count++;
                } else {
                    count--;
                }
            }
            return num;
        }
    };
    
    提交结果:
    算法分析与设计第五次作业(leetcode 中 Majority Element 题解)-LMLPHP
  • 1/3众数求解:
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int num1 = 0, num2 = 0;
            int count1 = 0, count2 = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if ( num1 == nums[i] ) {
                    count1++;
                } else if ( num2 == nums[i] ) {
                    count2++;
                } else if ( count1 == 0 ) {
                    num1 = nums[i];
                    count1++;
                } else if ( count2 == 0 ) {
                    num2 = nums[i];
                    count2++;
                } else {
                    count1--;
                    count2--;
                }
            }
            count1 = 0;
            count2 = 0;
            for (int i = 0; i < nums.size(); ++i)
            {
                if ( nums[i] == num1 ) count1++;
                else if ( nums[i] == num2 ) count2++;
            }
            vector<int> res;
            if ( count1 > nums.size()/3 ) res.push_back(num1);
            if ( count2 > nums.size()/3 ) res.push_back(num2);
            return res;
        }
    };
    
    提交结果:
    算法分析与设计第五次作业(leetcode 中 Majority Element 题解)-LMLPHP
    beat 98%+,上述解法基本上就是最优解法。
10-02 20:43