Day 3：747. Largest Number At Least Twice of Others

今日题目

题目连结：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