<算法(LeetCode)>六种方法求数组中的绝对众数

发表于 算法 2017-04-06 阅读数: 119

原题来自:LEETCODE。感谢:http://t.cn/R61A67j

定义:绝对众数就是一个数在一组数中个数超过1/2的数。比如给你一个长度为N的整形数组:

[13,12,53,12,23,343,12,12]

要求出他们之中出现次数超过N/2的元素(假定一个数组中必定会有这样的元素),你会怎么求?若你是暴力求解,时间复杂度为O(n^2),那就low啦!

下面是LeetCode上某位题友给出的六种算法,括号中是我测试出来的每个算法通过OJ的平均时间,我们来一个一个地讲解。

  1. 哈希表 (22ms)

  2. 排序法 (23ms)

  3. 随机数法 (19ms)

  4. 摩尔投票法 (19ms)

  5. 分治法 (26ms)

  6. 位操作法 (25ms)

下面一个一个地讲解。

一、哈希表法

代码: 

int majorityElement(std::vector<int> &nums){

        std::map<int, int>counter;

        for (int i = 0; i < nums.size(); ++i)

            if(++counter[nums[i]] > nums.size()/2)

                return nums[i];

    }

利用哈希表,将每个数值的次数存放起来,遇到一个就对应加一,直到这个数值的次数大于n/2为止(注意只可能有一个数,出现的次数大于n/2).

二、排序法 代码: 

int majorityElement(std::vector<int> &nums){

    nth_element(nums.begin(),nums.begin()+nums.size()/2,nums.end());

    return nums[nums.size()/2];

}

代码最简洁,仅仅两句。也很容易理解,运用了STL中的nth_element(). 通过调用nth_element(start, start+n, end)方法,可以使第n个大的数值的位置之前的元素都小于这个位置的元素,这个位置之后的元素都大于这个位置的元素。但是他们不一定是有序的。由于我们的绝对众数出现的次数大于n/2,所以排序后第n/2大的元素一定是这个绝对众数。

三、随机数法

代码:

int majorityElement(std::vector<int> &nums){

        srand((unsigned)time(NULL));

      //得到随机数种子

        while (1) {

            int counters = 0;

            int index = rand() % nums.size();

            for (int i = 0; i < nums.size(); ++i) {

                if (nums[index] == nums[i]){

                    ++counters;

                }

                if (counters > nums.size()/2){

                    return nums[index];

                }

            }

        }

    }

原理:随机找到一个数然后计算这个数组里这个数出现的次数,若大于n/2则返回这个数。我一开始以为这个算法会非常慢,因为它最坏情况是O(n^2),但出乎意料,44个测试的平均结果中,它几乎是最快的算法(19ms),和摩尔投票法相当。

四、摩尔投票法(动态规划)

代码:

int majorityElement(std::vector<int> &nums){

        int major = 0, counters = 0;

        for (int i = 0; i < nums.size(); ++i) {

            if(!counters){

                major = nums[i];

                counters = 1;

            }

            else

                counters += (major == nums[i]) ? 1:-1;

        }

        return major;//因为假设一定存在绝对众数,所以可以直接返回

    }

原理:定位major为数组中的某个数,遇到同样的数加一,不同的数减一,若为0则去掉这个定位,重新定位另外一个数,最后要么返回绝对众数,要么不存在绝对众数,由于题目中已经假设一定存在绝对众数,所以不存在的情况不需要考虑。

五、分治法

代码:

int majorityElement(std::vector<int> &nums){

        return majority(nums, 0, nums.size()-1);

    }

    int majority(std::vector<int> &nums,int left,int right){

        if (left == right) {

            return nums[left];

        }

        int mid = left + ((right - left) >> 1);

        int lm = majority(nums, left, mid);

        int rm = majority(nums, mid + 1, right);

        if(lm == rm){

            return rm;

        }

        return std::count(nums.begin() + left, nums.begin() + right + 1, lm) > std::count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;

    }

原理:通过分治的思想计算出左右两边出现次数最多的数,然后进行比较,看哪个出现的次数更多,返回次数更多的那一个。值得注意的是这里用到了STL里的count方法,它使用一对迭代器和一个值做参数,将值出现的次数返回。

PS:中间计算mid的时候用到了位操作符,>>1其实就是除以2. 不能直接(left+right)/2,因为left+right可能会溢出。

六、位操作法

代码:

       

int majorityElement(vector<int>& nums) {

        int major = 0;

        for (int i = 0,mask = 1; i < 32; ++i,mask <<= 1) {

            int bitCounts = 0;

            for (int j = 0; j < nums.size(); ++j) {

                if(nums[j] & mask) bitCounts++;

                if (bitCounts > nums.size()/2) {

                    major |= mask;

                    break;

                }

            }

        }

        return major;

    }

原理:这是最有趣的一个算法,它算的是每个数的bit(位),若所有数字的某个bit(位)的个数加起来大于一半,则绝对众数一定有这个位,把这个位的值加起来,最后得到的结果就是绝对众数。

PS:(major |= mask 中的 |= 是按位或,其实就相当于+=),(& 就是“与”运算符,返回两个数值中位置一样的位的值)

若还是无法理解,希望下面这张图能够帮助你理解这个算法。字丑见谅~

欢迎关注微信公众号:幻象客https://www.huanxiangke.com

欢迎进入极致分享:https://alltoshare.com

幻象客 二维码

Add comment