178-找出数组中出现次数超过一半的数

你的名字 2022-10-29 03:13 134阅读 0赞

**题目如下：**  
给定一个数组，数组中有一个元素长度超过了整个数组的一半。  
例如\[1, 1, 2, 1, 5\] 输出:1  
要求在O(N)的时间复杂度内，且空间复杂度O(1)

## 解题思路 ##

**士兵占领法则**  
算法思想如下，假设没个数字都代表一个队伍的士兵编号，那么题目可以转化为，有N个队伍的士兵，但是有一个队伍的士兵数量超过了总数的一半。  
**以下用占领山头的方式来求解：**

1、用一个指针来遍历士兵数组  
2、如果是一个空山头的话，那么直接将这个士兵放在山顶，表示这个队伍占领。  
3、接下来进行遍历，如果下一个来的是同样编号队伍的士兵，那么队伍壮大，继续占领。  
4、如果不是一个编号队伍的士兵，那么新的士兵和占领山头队伍的士兵(一个士兵)同归于尽。**这里的同归于尽是指一个对一个**  
最后还留在山头的，一定是哪个超过一半人数的队伍。

**代码实现加注释如下**

#include<stdio.h>
    
    int MoreThanHalfNum_Solution(int *arr,int len)
    {
        
        //士兵占领法
        if (len == 0)
        {
        
            return 0;
        }
        if (len == 1)
        {
        
            return arr[0];
        }
        int count = 0;//初始化计数值为0
        int index = -1; //初始化当前的士兵的代表值
    
        for (int i=0;i<len;++i)//遍历数组
        {
         
            if(count == 0)//如果计数为0，进入此语句
            {
        
                count++;//计数值为1
                index =arr[i];//将此时的值赋值给士兵代表的值
                continue;//提前进入下一次循环
            }
            if (arr[i] == index)//如果值和士兵代表的值相同，进入此语句
            {
        
                count++;//计数值加1
            }
            else//值和士兵的值不同
            {
        
                count--; //进行同归于尽
            }
        }
        count = 0;//重置为0
        for (int i=0;i<len;++i)//遍历数组
        {
        
            if (arr[i] == index)
            {
        
                count++;//记录最后存活的士兵的原有队伍的人数
            }
         }        
        return count * 2 > len ? index : 0;
        //如果最后存活的士兵的原有队伍人数超过总数的一半返回士兵代表的值
        //否则返回0
    }
    
    int main()
    {
        
    	int arr[]={
        1,1,2,1,5};
    	int len=sizeof(arr)/sizeof(arr[0]);
    	printf("%d\n",MoreThanHalfNum_Solution(arr,len));
    
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/beb120ddea23417282ee3147f6093af1.png