剑指OfferJZ28：数组中出现次数超过一半的数字-java版

阳光穿透心脏的1/2处 2022-08-30 11:48 34阅读 0赞

### 剑指OfferJZ28：数组中出现次数超过一半的数字-java版 ###

*   *   *  JZ28:数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\[1,2,3,2,2,2,5,4,2\]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000

### JZ28:数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\[1,2,3,2,2,2,5,4,2\]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000 ###

**法一：在遍历数组的过程中统计每个数字出现的次数是多少，用Map动态的存储每个数字出现的次数（降低了时间复杂度）**

public class jz28 { 
        //法一
        public int MoreThanHalfNum_Solution(int [] array) { 
            Map<Integer,Integer> map=new HashMap<>();
            int target=0;//用来存储出现次数最多的那个数字
            int sum=0;//用来存储出现次数最多的那个数字出现的次数
            for(int x:array){ 
                map.put(x,map.getOrDefault(x,0)+1);//更新当前位置数字x出现的次数 //getOrDefault()方法获取指定key对应对value，如果找不到key,则返回设置的默认值。
                if(sum<map.get(x)){ 
                    //当前位置的数字出现的次数比之前统计的target数字出现的数字大
                    sum=map.get(x);
                    target=x;
                }
    
            }
            if(sum>array.length/2){ //一个数字出现的次数超过数组长度的一半
                return target;//输出这个数字
            }
            return 0;
        }

**法二**：**假设有这样一个数满足出现的次数大于数组长度**，

*  将这个数一一和数组数字比较，如果相等，sum++；如果不相等sum–；（sum初始值设为0）
 *  如果到某一位置sum值=0，说明这个数不是当前位置之前出现次数最多的数，那么那么把之前假定的数换成当前位置的数,并将sum设为1，直到找到在某个位置之前出现次数最多的数
 *  最后将这个数与数组中的数一一比较，如果比较相同的次数大于数组的长度，那么这个数就是我们要找的

**例如**输入一个长度为9的数组a\[1,2,3,2,2,2,5,4,2\]  
假设1是满足条件（出现次数大于数组长度）的数，那么令target=1，sum置为0；

将target数组中的数一一比较，  
target=1和a\[0\]=1，相等，sum+1=1；  
target=1和a\[1\]=2，不相等，sum-1=0；说明target1不是在2这个位置之前出现次数最多的数，将target=2，sum置为1；  
target=2和a\[2\]=3，不相等，sum-1=0，说明target2不是在3这个位置之前出现次数最多的数，将target=3，sum置为1；  
target=3和a\[3\]=2，不相等，sum-1=0，说明target3不是在2这个位置之前出现次数最多的数，将target=2，sum置为1；  
target=2和a\[4\]=2，相等，sum+1=2，说明target2是2这个位置之前出现次数最多的数；  
target=2和a\[5\]=2，相等，sum+1=3，说明target2是2这个位置之前出现次数最多的数；  
target=2和a\[6\]=5,不相等，sum-1=2，说明target2是5这个位置之前出现次数最多的数；  
target=2和a\[7\]=4,不相等，sum-1=1，说明target2是4这个位置之前出现次数最多的数；  
target=2和a\[8\]=2,相等，sum+1=2，说明target2是2这个位置之前出现次数最多的数；  
所以找出出现次数最多的数应是2  
最后拿2和数组的每个数比较，看比较相等的次数有多少个，这里2比较与其相等的数的个数为5，大于数组长度9的一半，  
所以2最终是数组中出现次数大于数组长度一半的数

//法二
        public int MoreThanHalfNum_Solution(int[] array) { 
            if (array.length == 0) { 
                return 0;
            }
            int target = array[0];//假设满足条件（个数大于数组长度）的那个数字
            int sum = 0;
    
            //满足条件的数字存在，循环
            for (int x : array) { 
                if (x == target) { 
                    sum++;//一一和其他数字比较，如果相等，sum+1；
                } else { 
                    sum--;//如果不相等，sum-1；
                }
                if (sum == 0) { //说明target指向的数在当前位置之前不是出现次数最多的数
                    target = x;//把target更新为当前位置的数
                    sum = 1;
                }
            }
    
            if (check(target, array)) { //target出现的次数超过数组长度的一半
                return target;//返回这个数字
            }
            return 0;
        }
    
        //判断target这个数出现的次数是否超过数组长度的一半
        private boolean check(int target, int[] array) { 
            int sum=0;
            for(int x:array){ 
                if(x==target){ 
                    sum++;
                }
            }
            return sum>array.length/2;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][20210720133603802.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20220829/593f6eeb54524e44940b93aa3ece4151.png
[20210720133603802.gif_pic_center]: /images/20220829/9362c28dea714c46a93e1c8bf30e8d0d.png