牛客网--数组中出现次数超过一半的数字

朱雀 2022-05-06 03:10 183阅读 0赞

题目描述  
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

这道题我记得可以用某种O(n)方法很巧妙，但是忘了，只好用笨的方法

package 剑指offer;
    
    import java.util.HashMap;
    
    /**
     * Created by Administrator on 2018/10/12.
     */
    public class 数组中出现次数超过一半的数字 {
        public int MoreThanHalfNum_Solution(int [] array) {
            HashMap<Integer,Integer> map=new HashMap<>();
            for(int i=0;i<array.length;i++){
                if(map.getOrDefault(array[i],0)+1>array.length/2){
                    return array[i];
                }else{
                    map.put(array[i],map.getOrDefault(array[i],0)+1);
                }
            }
            return 0;
        }
    }

贴一下别人的代码，主要是利用结果数字超过数组长度一半的特点，保存两个值，即一个是数组中的一个数字，一个是次数  
当我们遍历到下一个数字的时候，

如果下一个数字和当前我们保存的数字相同，则次数加 1；

如果和当前我们保存的数字不同，则次数减 1；

当次数减到 0 的时候，我们将保存的数字改为当前遍历所处的位置，并将次数更改为 1。

int MoreThanHalfNum(int *arr, int len)
    {
        int result = arr[0];
        int count = 1;
    
        for(int i = 1; i < len; ++i)
        {
            if(arr[i] == result)
                count ++;
            else if(count == 0)
            {
                result = arr[i];
                count = 1;
            }
            else
                count --;
        }
        return result;
    }
    
    int main(int argc, char *argv[])
    {
        int arr[5] = {1, 0, 1, 2, 1};
    
        int num = MoreThanHalfNum(arr, 5);
        printf("The num is: %d\n", num);
    
        return 0;
    }