今日題目

題目連結：747. Largest Number At Least Twice of Others
題目主題：Array、Sorting

選擇這題的主要原因是它讓我想到了基本排序之一 Selection Sort 排序法，所以這次來分享一下 Selection Sort 的排序是怎麼運作的。

簡單說說 Selection Sort

Selection Sort是一種基本的排序陣列方法，用雙迴圈的方式來處理排序。以小到大的排序為例，Selection Sort的每一圈都會確認一個數字的位置，每一圈選擇目前未確認範圍的最小數字與這個範圍的最前面的數字調換位置，處理過程如下圖。

範例：nums = [32, 2, 18, 45, 15]

大紅方框是未確認範圍，每一圈會找到這個範圍的最小數字（上圖中的紅色數字），這個數字會與大紅方框中最前面的數字調換位置，跑完後就可以完成nums從小到大的排序。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

本題的目標是在一個nums的所有數字中，找到最大數字並且nums中其他數字的兩倍不能大於這個數字，最終輸出這個數字的位置(Index)。若找不到符合這條件的數字就回傳-1。

約束：

• 1 <= nums.length <= 50
• 0 <= nums[i] <= 100
• 最大的數字在nums中是唯一的

範例1

輸入：nums = [3,6,1,0]
輸出：1
解釋：6是這個陣列中最大的數字，其他數字兩倍也沒大於6，因此輸出為1這個位置。

範例2

輸入：nums = [1,2,3,4]
輸出：-1
解釋：最大的數字是4，但其中3的兩倍是6已經大於4了，因此回傳-1。

範例3

輸入：nums = [1]
輸出：0
解釋：若只有一個數字，可直接回傳0，因為沒有其他數字，所以也符合其他數字兩倍不能大於最大數這個條件。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告一個變數，用來紀錄最大數字的位置。
2. 先跑一個迴圈找到最大的數字的位置，記錄下來。
3. 再跑第二個迴圈，將每個數字乘2，跟最大的數字做比較。
   • 略過記錄的最大數字位置。
   • 若出現其他數字乘2後大於最大數字的狀況，把先前紀錄的位置改為-1，並直接結束這個迴圈。
4. 最後回傳紀錄到的位置。

圖解過程

範例：nums = [3, 6, 1, 0]

上圖中，第一迴圈找到了 6 這個最大的數字，並記錄了他的位置 1 。第二迴圈，因為記錄到最大數字的位置是 1 ，所以略過 1 的位置，而其他位置數字乘2後都沒有大於最大的數字 6 ，因此最後直接回傳 1 。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        # 紀錄最大數字的位置
        resultIndex = 0
        # 第一迴圈找出最大數字位置
        for i in range(1, len(nums)):
            if nums[resultIndex] < nums[i]:
                resultIndex = i
        # 第二迴圈檢查有沒有乘2大於最大數的數字
        for i in range(len(nums)):
            if resultIndex == i: continue
            if nums[resultIndex] < nums[i]*2:
                resultIndex = -1
                break
        return resultIndex

希望您今天能瞭解到...

1. Selection Sort 基本概念
2. 747. Largest Number At Least Twice of Others 解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：88. Merge Sorted Array