747. 至少是其他数字两倍的最大数
747. 至少是其他数字两倍的最大数
题目
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 theindex 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.
Constraints:
2 <= 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 。
提示:
2 <= nums.length <= 50
0 <= nums[i] <= 100
nums
中的最大元素是唯一的
解题思路
要判断数组中的最大值是否至少是数组中每个其他数字的两倍,只需要找出数组中最大的两个元素,判断最大值是否两倍大于第二大值即可。
初始化变量:
- 使用
max1
记录最大元素的索引,初始值为-1
。 - 使用
max2
记录第二大元素的索引,初始值为-1
。
- 使用
遍历数组:
- 如果当前数字比
nums[max1]
大,或max1 == -1
(还没有被赋值):- 将
max1
的值赋给max2
(即更新第二大值为之前的最大值)。 - 更新
max1
为当前数字的索引。
- 将
- 否则,如果当前数字比
nums[max2]
大,或max2 == -1
(还没有被赋值):- 更新
max2
为当前数字的索引。
- 更新
- 如果当前数字比
返回结果:
- 遍历结束后,判断
nums[max1]
是否至少是nums[max2]
的两倍:- 如果是,则返回
max1
。 - 否则返回
-1
。
- 如果是,则返回
- 遍历结束后,判断
复杂度分析
- 时间复杂度:
O(n)
,遍历数组一次。 - 空间复杂度:
O(1)
,使用了常量级额外空间。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var dominantIndex = function (nums) {
let max1 = -1,
max2 = -1; // max1为最大值索引,max2为第二大值索引
// 遍历数组,找到最大值和第二大值的索引
for (let i = 0; i < nums.length; i++) {
if (max1 == -1 || nums[i] > nums[max1]) {
max2 = max1; // 更新第二大值
max1 = i; // 更新最大值
} else if (max2 == -1 || nums[i] > nums[max2]) {
max2 = i; // 更新第二大值
}
}
// 检查是否满足最大值至少是其他值两倍的条件
return nums[max1] >= nums[max2] * 2 ? max1 : -1;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2154 | 将找到的值乘以 2 | [✓] | 数组 哈希表 排序 1+ | 🟢 | 🀄️ 🔗 |
2231 | 按奇偶性交换后的最大数字 | [✓] | 排序 堆(优先队列) | 🟢 | 🀄️ 🔗 |