Play this article
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
}
}