LeetCode 解題練習：Largest Number At Least Twice of Others

 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/largest-number-at-least-twice-of-others/

中文描述

給定一個有唯一最大值的整數陣列 nums ，請判斷此最大值元素是否為其他陣列元素值的兩倍以上，若有成立，請回傳此最大值在陣列中的索引位置。

範例一：

輸入 nums = [1, 2, 3, 6, 2, 3, 1]

輸出 3

因為 6 是最大值，且都為其他陣列元素[1, 2, 3]的兩倍以上。

範例二：

輸入 nums = [1, 2, 3, 4, 6]

輸出 -1

因為 6 是最大值，但 6 不是 4 的兩倍以上。

解法一：

Two Pass。

先找出最大值 largestNum 與索引位置 largestIdx。

判斷陣列中所有非最大值之元素是否有 largestNum 小於 nums[i] * 2，若有，回傳 -1。

Python Code

class Solution:

    def dominantIndex(self, nums: List[int]) -> int:

        largestNum = -1 # 最大值

        largestIdx = -1 # 最大值位置

       

        # 找最大值與索引位置

        for i in range(len(nums)):

            if nums[i] > largestNum:

                largestNum = nums[i]

                largestIdx = i

       

        for n in nums:

            if n != largestNum and 2*n > largestNum: # 非最大值元素的兩倍是否大於最大值

                return -1

       

        return largestIdx

解法二：

One Pass。

找出第一大值 largestNum、第二大值 secondNum，判斷 largestNum 是否有小於兩倍的 secondNum。

Python Code

class Solution:

    def dominantIndex(self, nums: List[int]) -> int:

        largestNum = nums[0] # 最大值設定為第一個陣列元素

        secondNum = 0 # 第二大值

        largestIdx = 0 # 最大值位置

       

        # 找最大值與索引位置

        for i in range(1, len(nums)):

            if nums[i] > largestNum:

                secondNum = largestNum

                largestNum = nums[i]

                largestIdx = i

            elif nums[i] > secondNum:

                secondNum = nums[i]

       

        if largestNum < 2 * secondNum:

            return -1

        return largestIdx