原文链接: https://leetcode-cn.com/problems/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.

中文题目

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

 

示例 1：

输入：nums = [3,6,1,0]
输出：1
解释：6 是最大的整数，对于数组中的其他整数，6 大于数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。

示例 2：

输入：nums = [1,2,3,4]
输出：-1
解释：4 没有超过 3 的两倍大，所以返回 -1 。

示例 3：

输入：nums = [1]
输出：0
解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。

 

提示：

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

通过代码

官方题解

方法：线性扫描

算法：

• 扫描数组找到唯一的最大元素 m，并记录它的索引 maxIndex。
• 再次扫描数组，如果我们找到 x != m，m < 2*x，我们应该返回 -1。
• 否则返回 maxIndex

[ ]
class Solution(object):
    def dominantIndex(self, nums):
        m = max(nums)
        if all(m >= 2*x for x in nums if x != m):
            return nums.index(m)
        return -1

[ ]
class Solution {
    public int dominantIndex(int[] nums) {
        int maxIndex = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > nums[maxIndex])
                maxIndex = i;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (maxIndex != i && nums[maxIndex] < 2 * nums[i])
                return -1;
        }
        return maxIndex;
    }
}

复杂度分析

• 时间复杂度：$O(N)$。$N$ 指的是 nums 的大小
• 空间复杂度：$O(1)$，只用了常数空间。

统计信息

通过次数	提交次数	AC比率
46635	111213	41.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言