剑指offer28 出现次数超过一半的元素

剑指offer28

3、位运算方法实现

class Solution {
public:
    //位运算实现：时间复杂度O(n*max)  空间复杂度O(1)   max为数据类型长度，这里是int(32位为32)：
    //目标:找到出现次数最多的数据，并判断该数据出现次数是否超过一半
    //分析：以32位int类型为例，出现次数超过一半的元素，它每一位的状态出现都是超过一半的
    //如：5是出现最多元素，5=0101，则所有元素 第一位出现最多情况是1   第二位最多情况是0  第三位最多情况是1..依次类推32位
    //又因为每一位非0即1,所以若1出现超过一半，0出现肯定少于一半，最多元素此位为1;若1出现次数少于一半，则最多元素此位为0
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size()==1) return numbers[0];
        int ret=0; //最多元素,初始所有位均为0，然后不断判断每一位具体是多少，加入
        int mask=1; //判断位辅助
        int len=numbers.size();
        for(int i=0;i<8*sizeof(int);i++) //sizeof(int)=int字节数，1字节=8位
        {
            int count=0; //记录某位1出现次数
            for(int j=0;j<len;j++)
            {
                if((numbers[j]&mask)!=0)
                    ++count;
            }
            if(count==(len-count)) //1等于一半，0等于一半，显然这组数据中没出现超过一半的元素提前剪枝
                return -1;
            if(count>(len-count)) //1超过一半，出现次数超过一半的元素可能存在，最后求出后再检查
            {
                ret|=mask; //ret的此位 状态为1  0超过一半状态为0，已默认不需要处理 这里用异或^ 和 或| 都行
            }
            mask<<=1; //左移1
        }
        int num=0;
        for(int x:numbers) //检查求得元素是否出现次数超过一半，若不是，则不存在出现次数超过一半的元素
        {
            if(x==ret)
                ++num;
        }
        if(num>len/2)
            return ret;
        else
            return -1;
    }
};

4、摩尔投票法实现

class Solution {
public:
    /*
    摩尔投票法:
              元素两两对抗相消，最后剩下的元素一定是出现超过一半的元素。最后检查剩下的那个元素出现的次数是否超过一半，
              若超过为最终结果；若不超过，该数组中没有出现次数超过一半元素。
    count：表示当前候选人数量（对抗相消后活下来的）
    cand:  当前候选人(元素)
    N:当前候选人全部死亡(全部相消了count=0)
    相消规则：候选人x=num[k],若下一个元素与候选人相同,候选人不变,count+1；若不同，count-1,
             若count=0候选人x=N，即此时无候选人，等到下一个元素Z来临重新开始，Z为候选人，count=1
    */
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    //摩尔投票法
        int cand=numbers[0]; //候选人，开始为第一个元素
        int count=1;//当前相消后候选人数量，开始候选人1个
        int len=numbers.size();
        for(int i=1;i<len;i++)
        {
            if(count==0) //候选人为空，此时count==0,cand=INT_MAX,
            {
                cand=numbers[i];//候选人为空时，下一个元素无论是啥都是候选人，候选人数量置1即count=1
                count=1;
            }
            else if(cand==numbers[i]) //候选人不为空，且和下一位相同
                ++count;
            else //候选人不为空，且和下一位不同
            {
                --count;
                if(count==0)//候选人为空，设置一个取不到的数(一般可以取最大值)
                    cand=INT_MAX; //其实改不改不重要，因为count=0也表示候选人为空，二者同时存在
            }
        }
        int num=0;
        for(int i=0;i<len;i++) //检查超过一半的元素是否存在，若存在就是cand，所以检查cand是否符合即可
        {
            if(cand==numbers[i])
                ++num;
        }
        if(num>len/2) //存在，cand符合
            return cand;
        else //不存在，返回-1
            return -1;
    }
};