寻找水王数 Java实现

Java实现"/>

寻找水王数 Java实现

水王数定义

在一个整形的数组中，如果某个数出现的次数大于数组长度的1/2那么这个数就是水王数。

思路

1.可以使用HashMap存储数组中每个数出现的次数，最后选出数量大于数组长度1/2的数即可。

    public static int findWaterKing2(int[] num){// 存放数组中的数出现的次数Map<Integer,Integer> map = new HashMap<>();int len = num.length;for (int i = 0;i<len;i++){// 如果map中存在这个数，那么把这个数出现的次数加1if (map.containsKey(num[i])){map.put(num[i],map.get(num[i])+1);}else// 否则将这个数 的value设置为1map.put(num[i],1);}// 遍历字典Iterator<Map.Entry<Integer,Integer>> iterator = map.entrySet().iterator();// 计算数组长度的1/2为多少int temp = len >> 1;while (iterator.hasNext()){Map.Entry<Integer,Integer> entry = iterator.next();// 如果大于数组长度1/2则返回该数if (entry.getValue()>temp)return entry.getKey();}return -1;}

2.同时删除俩个相邻并且不相同的数，最后剩下的数就为水王数，因为水王数的数量大于数组总数的1/2，所以就算其余数每个都消去水王数，最后还能至少剩下一个。不过需要注意没有水王数的情况，以及数组长度为偶数刚好全部删除了的情况，最后做个判断，如果没有剩余的数了说明不存在水王数，如果有剩余的数，则计算剩余的数出现的次数，如果小于数组长度1/2也说明不存在水王数。

    public static int findWaterKing(int[] num){int blood = 0;int current = -1;int len = num.length;for (int i = 0;i<len;i++){if(blood == 0){current = num[i];blood ++ ;}else {if (current == num[i]){blood ++;}elseblood --;}}if(blood == 0)return -1;// 最后判断一下剩下的数是否超过了数组长度的1/2int curLen = 0;for (int i = 0;i<len;i++){if (num[i]==current)curLen ++;}if(curLen > len*0.5)return current;elsereturn -1;}