LeetCode演算法題-Largest Number At Least Twice of Others（Java實現）
這是悅樂書的第308 次更新，第328 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第177題（順位題號是747）。在給定的整數陣列中，總有一個最大的元素。查詢陣列中的最大元素是否至少是陣列中每個其他數字的兩倍。如果是，則返回最大元素的索引，否則返回-1。例如：
輸入：nums = [3,6,1,0]
輸出：1
說明：6是最大的整數，對於陣列x中的每個其他數字，6是x的兩倍多。 值6的索引是1，所以我們返回1。
輸入：nums = [1,2,3,4]
輸出：-1
說明：4至少不是3的值的兩倍，所以我們返回-1。
注意：
-
nums的長度在[1,50]範圍內。
-
每個nums [i]將是[0,99]範圍內的整數。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
題目的要求是返回最大數的索引，所以需要先將最大數找出來，並記錄下其索引。然後在次遍歷陣列中的元素，將最大數之外的其他數都乘以2和最大數比較(在此處我是使用位移處理)，如果大於就返回-1，如果其他元素都滿足條件，就返回之前記錄的最大數的索引。
public int dominantIndex(int[] nums) {
int index = 0, max = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
index = i;
}
}
for (int i=0; i<nums.length; i++) {
if (nums[i] != max && nums[i]<<1 > max) {
return -1;
}
}
return index;
}
03 第二種解法
我們還可以只使用一次迴圈來解決。並非需要使用每一個元素乘以2後再去和最大元素比較，只需要用第二大的數去比較就行，如果第二大的數不能滿足條件，就可以直接做判斷了。比如[2,3,4]，3乘以2等於6大於4，不符合題目要求，就不需要比較2了。
public int dominantIndex(int[] nums) {
int max = 0, second = 0, index = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] > max) {
second = max;
max = nums[i];
index = i;
} else if(nums[i] > second) {
second = nums[i];
}
}
return second<<1 <= max ? index : -1;
}
04 小結
演算法專題目前已日更超過五個月 ，演算法題文章177 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！