数组中出现次数超过一半的数字_28

名字是乱打的

发布于 2021-12-23 18:21:07

1840

发布于 2021-12-23 18:21:07

文章被收录于专栏：软件工程

方法1 ,利用排序

可以升序排序如果存在这个数,那么这个数一定在排序后的中间位置,且前面的数都是这个数字;但是这个用到了排序,最快时间复杂度也是nlog2n

方法2 守阵地法

思路:守阵地,遇到队友队伍加1,遇到敌人,同归于尽一个😏,就是这么猛

首先用一个数字survivor来保存幸存者方,用一个数字count来计算幸运者幸运值规则:如果遇到相同数字代表相同阵营,surCount++; 如果遇到不同数字,则同阵营幸存者surCount--; 如果count=0,则同阵营幸存者被取代.

注意

如果存在超过一半的数字,那么这个数字肯定是幸存者,但是幸存者不一定是个数超过一般的那个.比如12213,幸存者是3,但是3个数没有超过一半.因此我们在得到幸存者后要进行验证
终极理解 为什么说如果存在超过一半的数字,那么这个数字肯定是幸存者? 因为如果极端的说,若其个数超过一半了,那么就算间隔着如12131514161,其他数字全由1出力干掉不用其他数字帮忙,最后也可以幸存1个

 public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length==1){
            return array[0];
        }

        int survivor = array[0];
        int surCount=1;
        for (int i = 0; i < array.length; i++) {
            if (surCount==0){
                survivor=array[i];
                surCount++;
            }else if (survivor!=array[i]) {
                surCount--;
            }else  if (survivor==array[i]){
                surCount++;
            }
        }

        int count=0;
        for(int i=0;i<array.length;i++){
            if (array[i]==survivor){
                count++;
            }
        }

        if (count>array.length/2){
            return survivor;
        }else {
            return 0;
        }
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/4/20 下，如有侵权请联系 cloudcommunity@tencent.com 删除

count