超級水王問題：給你一個陣列，出現次數大于陣列長度的一半的元素稱之為
水王數，怎么能快速找到水王數？記憶體限制：時間復雜度
O(n)，額外空間復雜度O(1)——也就是遍歷陣列的次數為有限次，申請的變數數為有限個參考鏈接：https://www.bilibili.com/video/BV11v411G7xR?from=search&seid=11400709428790899860
方式一：暴力法
暴力法的思想很簡單，用一個hashmap來存放陣列中每個元素及其對應的數量，最后遍歷hashmap判斷有無元素數量大于陣列長度一半，有則直接回傳水王數，否則回傳-1
public static int verify(int[] arr) {
if (arr == null || arr.length == 0)
return -1;
//新建hashmap用于存放陣列中每個元素及其對應的數量
HashMap<Integer, Integer> hashMap = new HashMap<>();
//遍歷陣列的每個元素
for(int num:arr){
//如果hashmap中包含該元素,則將該元素的數量+1
if(hashMap.containsKey(num))
hashMap.put(num,hashMap.get(num)+1);
//如果hashmap中不包含key,則將該元素的數量置為1
else
hashMap.put(num,1);
}
//遍歷hashmap中每一個entry<k,v>
for(Map.Entry<Integer,Integer> record:hashMap.entrySet()){
if(record.getValue()>(arr.length>>1))//這里采用位運算,速度快
//回傳水王數
return record.getKey();
}
return -1;
}
顯然，該方法不符合題目的限制，由于使用了hashmap，所以額外的空間復雜度為O(N)
方法二
如何使用有限變數遍歷有限次數來完成呢？
思路：從陣列第一個元素開始，依次刪掉兩個不同的數，最后如果有水王數的話，它會剩下來（反過來不成立，也就是剩下來的數不一定是水王數）
如上圖所示，依次洗掉兩個不同的元素，相同則不洗掉，最后只剩下3即是水王數
但請注意，剩下的不一定是水王數，比如：12345，刪掉12、34還剩5，但是5不是水王數
這是什么原理呢？我們假設一個陣列中有水王數，由于水王數的個數大于所有元素個數的一半，所以如果拿一個非水王數抵消一個水王數，最后還是會剩下水王數；上述洗掉不同元素的程序就是如此，還可能會存在兩個非水王數互相抵消的情況，這樣水王數剩下的會更多，
因此我們的演算法可以轉換為以下兩步：
- 依次洗掉陣列中兩個不同的數
- 判斷是否有數剩余，如果沒有數剩余，則不存在水王；如果有數剩余，我們再遍歷一次陣列，計算該數的真實的出現次數與陣列長度的一半進行比較判斷是否為水王數
怎么實作呢？我們只需要兩個變數，變數一candidate作為候選用來存放可能的水王數，變數二hp用來存放其剩余個數，按如下規則遍歷陣列：
hp=0代表沒有candidate候選數；hp>0代表有candidate候選數- 如果沒有candidate，則設定當前數賦予candidate，即將當前數作為候選數，hp設定為1
- 如果有candidate，判斷當前數是否等于candidate，相等則hp+1，不相等則hp-1
最后判斷看hp是否為0，如果不為0，則代表有可能的水王數，再進行計數判斷即可
代碼實作：
public static int waterKing(int[] arr) {
if (arr == null || arr.length == 0)
return -1;
int candidate = 0;
int hp = 0;
for (int cur : arr) {
if (hp == 0) {//沒有候選,則將當前數設為候選
candidate = cur;
hp++;
} else if (cur != candidate)//有候選且當前數!=侯選數
hp--;
else//有候選且當前數=候選數
hp++;
}
//沒有候選數剩余,則沒有水王數
if (hp == 0)
return -1;
//計算候選數在陣列中的元素個數
int count = 0;
for (int num : arr) {
if (num == candidate)
count++;
}
//如果候選數元素個數>陣列長度的一半則回傳,否則回傳-1
return count > (arr.length >> 1) ? candidate : -1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287243.html
標籤：其他
上一篇：美少女博客轉型