每日一题《剑指offer》数组篇之数组中出现次数超过一半的数字

终有救赎

发布于 2023-10-16 10:20:18

1530

发布于 2023-10-16 10:20:18

文章被收录于专栏：多线程

今日题目链接:数组中出现次数超过一半的数字

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

难度：简单

描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围

数据范围：0n≤50000，数组中元素的值 0≤val≤10000

要求：空间复杂度：O(1)，时间复杂度 O(n)

举例

解题思路

本题有以下三种方法可解：

方法一：首先对数组进行排序，在一个有序数组中，次数超过一半的必定是中位数，那么可以直接取出中位数，然后遍历数组，看中位数是否出现次数超过一半，这取决于排序的时间复杂度，最快为O(nlogn)。

方法二：遍历数组，用 HashMap 保存每个数出现的次数，这样可以从map中直接判断是否有超过一半的数字，这种算法的时间复杂度为O(n)，但是这个性能提升是用O(n)的空间复杂度换来的。

方法三（最优解法）：根据数组特点得到时间复杂度为O(n)的算法。根据数组特点，数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数之和还要多。 因此，我们可以在遍历数组的时候设置两个值：一个是数组中的数result，另一个是出现次数times。当遍历到下一个数字的时候，如果与result相同，则次数加1,不同则次数减一，当次数变为0的时候说明该数字不可能为多数元素，将result设置为下一个数字，次数设为1。这样，当遍历结束后，最后一次设置的result的值可能就是符合要求的值（如果有数字出现次数超过一半，则必为该元素，否则不存在），因此，判断该元素出现次数是否超过一半即可验证应该返回该元素还是返回0。这种思路是对数组进行了两次遍历，复杂度为O(n)。

编程实现(java)

//思路2：用hashmap保存每个数出现的次数
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null)
            return 0;
        Map<Integer,Integer> res=new HashMap<>();
        int len = array.length;
        for(int i=0;i<array.length;i++){
            res.put(array[i],res.getOrDefault(array[i],0)+1);
            if(res.get(array[i])>len/2)
                return array[i];
        }
        return 0;
    }

    //思路3：根据数组特点得到时间复杂度为O(n)的算法
    public int MoreThanHalfNum_Solution(int [] array) {
    	if(array==null||array.length==0)
            return 0;
        int len = array.length;
        int result=array[0];
        int times=1;
        for(int i=1;i<len;i++){
            if(times==0){
                result=array[i];
                times=1;
                continue;	//continue的意思是结束本次循环，也就是本次循环的下面代码不执行了
            }
            
            if(array[i]==result)
                times++;
            else
                times--;
        }
        //检查是否符合
        times=0;
        for(int i=0;i<len;i++){
            if(array[i]==result)
                times++;
            if(times>len/2)
                return result;
        }
        return 0;
    }