747. Largest Number At Least Twice of Others

題目敘述

You are given an integer array nums where the largest integer is unique.

Determine whether the largest element in the array is at least twice as much as every other number in the array. If it is, return the index of the largest element, or return -1 otherwise.

Example 1:

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest integer.
For every other number in the array x, 6 is at least twice as big as x.
The index of value 6 is 1, so we return 1.

Example 2:

Input: nums = [1,2,3,4]
Output: -1
Explanation: 4 is less than twice the value of 3, so we return -1.

Example 3:

Input: nums = [1]
Output: 0
Explanation: 1 is trivially at least twice the value as any other number because there are no other numbers.

Constraints:

• 1 <= nums.length <= 50
• 0 <= nums[i] <= 100
• The largest element in nums is unique.

Hint 1:

Scan through the array to find the unique largest element m, keeping track of it's index maxIndex. Scan through the array again. If we find some x != m with m < 2*x, we should return -1. Otherwise, we should return maxIndex.

題目翻譯

要在陣列 nums 中找出最大值，但是其最大值至少要比其它的值大兩倍才行。

解法解析

因為要大兩倍，所以其實就是最大值跟次大值做比較而已。因此這題的解法滿單純的，就是遍歷一次，然後用兩個變數做紀錄，在最後判斷有沒有大於兩倍就好了。

解法範例

Go

func dominantIndex(nums []int) int {
    if len(nums) == 0 {
        return -1
    }

    var (
        largest       int = -1
        secondLargest int = -1
        maxIndex      int
    )

    for i, val := range nums {
        if val >= largest {
            secondLargest = largest
            largest = val
            maxIndex = i
        } else if val > secondLargest {
            secondLargest = val
        }
    }

    if largest >= secondLargest*2 {
        return maxIndex
    }
    return -1
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var dominantIndex = function (nums) {
    if (nums.length === 0) {
        return -1;
    }
    let largest = -1,
        second = -1,
        maxIdx = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > largest) {
            second = largest;
            largest = nums[i];
            maxIdx = i;
        } else if (nums[i] > second) {
            second = nums[i];
        }
    }

    return largest >= second * 2 ? maxIdx : -1;
};

Kotlin

class Solution {
    fun dominantIndex(nums: IntArray): Int {
        if (nums.size == 0) return -1

        var largest = -1
        var secondLargest = -1
        var largestIndex = 0

        for ((i, value) in nums.withIndex()) {
            if (value > largest) {
                secondLargest = largest
                largest = value
                largestIndex = i
            } else if (value > secondLargest) {
                secondLargest = value
            }
        }

        return if (largest >= secondLargest * 2) largestIndex else -1
    }
}

PHP

class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function dominantIndex($nums)
    {
        if (count($nums) == 0) {
            return -1;
        }
        $max = max($nums);
        $maxIndex = array_search($max, $nums);
        foreach ($nums as $idx => $value) {
            if ($idx == $maxIndex) {
                continue;
            }
            if ($value * 2 > $max) {
                return -1;
            }
        }
        return $maxIndex;
    }
}

Python

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return -1

        largest = -1
        second = -1
        maxIdx = 0

        for i, val in enumerate(nums):
            if val >= largest:
                second = largest
                largest = val
                maxIdx = i
            elif val > second:
                second = val

        return maxIdx if largest >= second * 2 else -1

Rust

Swift

class Solution {
    func dominantIndex(_ nums: [Int]) -> Int {
        guard nums.count > 1 else { return 0 }

        var largest = -1
        var secondLargest = -1
        var largestIndex = 0

        for (i, val) in nums.enumerated() {
            if val >= largest {
                secondLargest = largest
                largest = val
                largestIndex = i
            } else if val > secondLargest {
                secondLargest = val
            }
        }

        return largest >= 2 * secondLargest ? largestIndex : -1
    }
}