What is the pattern for solving 'Largest Number At Least Twice of Others'?

The pattern involves scanning the array twice: first to find the largest element and its index, and second to verify if it's at least twice as large as every other element.

How should I optimize the solution for this problem?

The solution can be optimized by scanning the array twice to find the largest element and check the twice condition, keeping the time complexity at O(n).

Can the array length affect the performance of my solution?

Yes, as the array length increases, the number of operations required to find and compare the largest element will increase linearly, making the solution's performance dependent on the array's size.

What happens if the array has duplicate values?

The problem guarantees that the largest element is unique, so duplicates won’t affect the solution. The uniqueness condition simplifies the problem.

Is sorting necessary for this problem?

Sorting is not necessary. A simple two-pass approach to find the largest element and verify its twice condition is sufficient and more efficient.

#747

Easy

auto_awesome数组·排序

LeetCode 题解工作台

至少是其他数字两倍的最大数

给你一个整数数组 nums ，其中总是存在唯一的一个最大整数。请你找出数组中的最大元素并检查它是否至少是数组中每个其他数字的两倍。如果是，则返回最大元素的下标，否则返回 -1 。示例 1：输入： nums = [3,6,1,0] 输出： 1 解释： 6 是最大的整数，对于数组中的…

数组排序

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

lightbulb

解题思路

方法一：遍历

我们可以遍历数组 $nums$ ，找到数组中的最大值 $x$ 和第二大的值 $y$ ，如果 $x \ge 2y$ ，则返回 $x$ 的下标，否则返回 $-1$ 。

我们也可以先找到数组中的最大值 $x$ ，同时找到最大值 $x$ 的下标 $k$ 。然后再遍历一次数组，如果发现 $k$ 以外的元素 $y$ 满足 $x < 2y$ ，则返回 $-1$ 。否则遍历结束后返回 $k$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        x, y = nlargest(2, nums)
        return nums.index(x) if x >= 2 * y else -1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to identify the largest element in a single scan of the array.
question_mark
Understanding of how to compare array elements efficiently in two passes.
question_mark
Attention to detail in ensuring that all elements are checked against the largest element.

warning

常见陷阱

外企场景

error
Not verifying that the largest element is at least twice as large as all others, leading to incorrect results.
error
Overcomplicating the solution with unnecessary steps or additional data structures.
error
Misunderstanding the problem and incorrectly handling cases where the largest element doesn’t meet the twice condition.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider cases where the array contains only two elements.
arrow_right_alt
Handle arrays with all elements being the same, except for the largest one.
arrow_right_alt
What if the array contains very large or very small numbers? Ensure that edge cases are considered.

help

常见问题

外企场景

继续练习

#757 设置交集大小至少为2 #768 最多能完成排序的块 II #769 最多能完成排序的块