超級水王數：

描述：
在一個數組中，如果存在一個數，在該數組中出現的次數大于數組長度的一半，那么這個數就是超級水王數

暴力解決：
使用HashMap來存儲每個元素出現的次數，最后判斷出現次數大于數組長度一半的元素并返回。

代碼如下：

public static void Hash(int[] arr){if(arr == null || arr.length == 0){System.out.println("數組為空，沒有水王數");}int n = arr.length;HashMap<Integer,Integer> map = new HashMap<>();for(int i : arr){if(map.containsKey(i)){map.put(i,(map.get(i) + 1));}else{map.put(i, 1);}}for(Map.Entry<Integer,Integer> record : map.entrySet()){if(record.getValue() > (n >> 1)){System.out.println("水王數：" + record.getKey());}}}

但使用HashMap的空間復雜度是O(n)。可不可以得到一個空間復雜度為O(1)的算法呢？

答案是有的。

思路：
從數組第一個元素開始，依次刪掉兩個不同的數，最后如果有水王數的話，它會剩下來（反過來不成立，也就是剩下來的數不一定是水王數）。
所以我們需要第二次遍歷數組，來判斷剩下的數的數量超過數組的一半沒。

如何實現呢？

將問題轉換為以下兩步：

1、依次刪除數組中兩個不同的數
2、 判斷是否有數剩余。如果沒有數剩余，則不存在水王；如果有數剩余，我們再遍歷一次數組，計算該數的真實的出現次數與數組長度的一半進行比較判斷是否為水王數

我們需要定義兩個變量：變量1：king，來決定當前的水王數候選者。變量2：hp。水王數的生命值，也就是水王數的數量。

如果生命值為0，那么遍歷的當前的元素就為水王數。如果生命值不為0，并且當前的元素和水王數候選者并不相同，該元素就會和水王數PK，使HP減一。如果當前的元素和水王數相同，就會增強水王數的實力，使HP+1。

遍歷完數組后，如果HP不為0，就再進行一次遍歷。統計該水王數候選者在數組中出現的次數，如果總次數大于數組長度的一半，那么就返回該水王數。
否則返回-1.

代碼實現：

//候選者法：public static void WaterKing(int[] arr){if(arr == null || arr.length == 0){System.out.println("數組為空，沒有水王數");}int king = 0; //水王數候選者int HP = 0; //代表生命值，每當數組中有相同的數時，生命值加一for(int num : arr){ //遍歷數組if(HP == 0){ //如果生命值為0，候選者為當期的數king = num;HP = 1; //生命值為1}else if(num != king){ //如果有候選者，且當前值和候選者的值不一樣，生命值減一HP--;}else{ //如果遇到了相同的數，生命值加一HP++;}}if(HP == 0){ //如果生命值為0，則表示沒有水王數System.out.println("沒有水王數");}//再次遍歷int count = 0;int n = arr.length;;for(int i : arr){if(i == king){count++;}}if(count > (n >> 1)){System.out.println("水王數為：" + king);}else{System.out.println("沒有水王數");}}

總結

以上是生活随笔為你收集整理的超级水王问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。