leetcode-169-Majority Element

2018-06-17 20:50:44来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述:

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.

 

要完成的函数:

int majorityElement(vector<int>& nums) 

 

说明:

1、这道题目给定长度为n的数组,要求输出某个元素的值,该元素出现次数超过?n/2?。

2、不得不说,这道题目有很多种解法,最暴力的莫过于双重循环,统计各个元素的出现次数,统计到出现?n/2?次的就停止,然后输出。

3、但除此之外,我们还可以尝试快速排序,排序完数组中坐标为?n/2?的就是我们要输出的元素。快排代码如下:

#include<algorithm>
int majorityElement(vector<int>& nums)
{
    sort(nums.begin(),nums.end());
    return nums[nums.size()/2];
}

sort是头文件<algorithm>中的函数,采用的是类似于快排的方法,该函数一共有三个参数。

第一个参数是数组指针,第二个参数是数组中最后一项的下一项的指针。

最后一个参数是排序方法,可以使用c++内置的比较函数。记得要include<funtional>,然后less<int>()表示从小到大排序,这也是默认排序方法,还可以是greater<int>(),从大到小排序。

最后一个参数还可以是自定义函数,如下是从大到小的排序:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool compare(int a,int b)//自定义比较函数
{
    return a>b;
}
int main()
{
    vector<int>v={1,2,3,4,5,6,7,8,9};
    sort(v.begin(),v.end(),compare);//以函数名作为第三个参数,进行快排
    for(vector<int>::iterator iter=v.begin();iter<v.end();iter++)//vector迭代器的使用
    cout<<*iter<<" ";
    return 0;
}

快排算法beats 20% of cpp submissions

 

4、对3中的算法做些优化,我们是否可以只做几遍快速排序,当得到?n/2?位置的最终值时就停下呢?(我们知道快排每一遍排序都可以得到一个最终值)这样我们可以大大减少所需要的时间。

刚好c++中有nth_element函数,代码如下:

int majorityElement(vector<int>& nums) 
{
        nth_element(nums.begin(),nums.begin()+ nums.size()/2, nums.end());//这个函数进行部分快排,直到第二个参数表示的位置已经得到最终值
        return nums[nums.size()/2];
} 

nth_element原理如下:

首先选定一个基准值,比如我们常用的nums[0],进行第一次快排,nums[0]的值最终放到了mid位置上,这时候mid左边的值都比它小,右边的值都比它大。

接着看一下第二个参数表示的位置的值在mid的哪一边,然后对这一边继续进行快排,mid的另一边就不理了。

重复操作,直到第二个参数表示的位置的值成为最终值。

这种算法beats 79.89% of cpp submissions

 

5、上面我们一共说了三种算法,暴力双重循环,快排,部分快排。除此之外,在评论区还见到了其他三种惊为天人的算法,下面逐一与大家分享。

6、随机算法

代码如下,应该不难看懂~

#include<ctime>
int
majorityElement(vector<int>& nums) { int n = nums.size(); srand(unsigned(time(NULL)));//以当前时间作为一个种子,NULL表示产生的时间值不被计算机存储,只被当前语句处理。生成的值要转化为unsigned int类型作为srand的参数。 while (true) { int idx= rand() % n; int candidate = nums[idx]; int counts = 0; for (int i = 0; i < n; i++) if (nums[i] == candidate) counts++; if (counts > n / 2) return candidate; } }

  这个算法虽然最差时间复杂度是无穷大,但是实际过程中由于我们要找的数占据了数组的一半以上,所以随机生成这个数的概率还是很高的。

  实测了五次,最好的是beat 97.24% of cpp submissions,最差的是11.17% of cpp submissions。

  这种做法还是挺新鲜的,碰到做不出的题目也可以用这种方法水过题目测试点。

 

7、成对抵消算法

先附上代码,很简洁的~

int majorityElement(vector<int>& nums) 
{
int major, counts = 0, n = nums.size(); for (int i = 0; i < n; i++)
    {
if (!counts) //如果counts为0则改变major值,同时赋counts为1
       { major
= nums[i]; counts = 1; } else counts += (nums[i] == major) ? 1 : -1; } return major; }

由于数组中,我们要找的元素出现了?n/2?次,因此我们可以,从数组中找出能成对抵消的元素,抵消到最后剩下的那一个就是我们要找的数了。

例如:数组为[2,1,2,3,2]

第一次循环,major=2,counts=1

第二次循环,counts=0

第三次循环,major=2,counts=1

第四次循环,counts=0

第五次循环,major=2,counts=1

最后的major就是我们要的数。

 

再举一个例子,数组为[3,3,1,3,1]

第一次循环,major=3,counts=1

第二次循环,counts=2

第三次循环,counts=1

第四次循环,counts=2,

第五次循环,counts=1

因为counts不会退到0,所以major也就不会改变,最后输出major=3

 

这种算法时间复杂度为O(n),是一种极为简单而又精彩的做法。

实测beats 79.89% of cpp submissions。

 

8、位操作算法

看到discuss区中大神提出了7中的成对抵消算法,笔者就想起了前几天做过的异或题目,相同的值可以抵消,但是这道题并不是相同值抵消,而是不同值,所以不能使用异或~

但是我们仍然可以使用位操作来完成这道题目。

我们要找的数出现了?n/2?次以上,从二进制的角度来看,也就是32位中的某一位出现了?n/2?次以上,根据这一点我们可以采取如下操作

int majorityElement(vector<int>& nums) 
{
        int major = 0, n = nums.size();
        for (int i = 0, mask = 1; i < 32; i++, mask <<= 1)
        {
            int bitCounts = 0;
            for (int j = 0; j < n; j++)
            {
                if (nums[j] & mask) //在mask代表的这一位上为1
            bitCounts++; if (bitCounts > n / 2) //总的出现次数在n/2以上,则我们要找的数在这一位上有出现,major要“或”上这一位 { major |= mask; break;//跳出内层循环 } } } return major; }

 

总结:

这虽然是一道简单的题目,但发散开来,我们可以总结出这么多种方法:

1、暴力双重循环法

2、快排

3、部分快排

4、随机算法

5、成对抵消算法

6、位操作法

其中的成对抵消算法最稳定,结果也优秀。

部分快排结果也挺优秀,不过花费的时间不会很稳定。

随机算法成绩可以很优秀,也可以很糟糕,实际体验就看命了,不过好处就是很简单地解出一些题目,trick。

快排时间复杂度高一点,传统解法。

暴力双重循环是最简单但是也最高时间复杂度的解法。

位操作也是双重循环,跟暴力解法差不多。

笔者还是最喜欢成对抵消的做法,简单稳定~

 

这道题目还有其他算法,由于时间关系就不介绍了,详见以下两个网址:

https://leetcode.com/problems/majority-element/discuss/51612/6-Suggested-Solutions-in-C++-with-Explanations

https://leetcode.com/problems/majority-element/solution/

本文章几种算法、思路和代码都来源于这两个网页介绍的内容。侵删。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:洛谷P2851 [USACO06DEC]最少的硬币The Fewest Coins(完全背包+多

下一篇:27.C++- 智能指针