在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


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

题目

在一个给定的数组 nums 中,总是存在一个最大元素 。

查找数组中的最大元素是否至少是数组中每个其他数字的两倍。

如果是,则返回最大元素的索引,否则返回-1。

示例1:

输入: nums = [3, 6, 1, 0]
输出: 1
解释: 6是最大的整数, 对于数组中的其他整数,
6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.

示例2:

输入: nums = [1, 2, 3, 4]
输出: -1
解释: 4没有超过3的两倍大, 所以我们返回 -1.

提示:

  1. nums 的长度范围在[1, 50].
  2. 每个 nums[i] 的整数范围在 [0, 100].

解题思路

思路 1:

这道题可以通过两次遍历暴力解决。

1. 第一次遍历,找出数组元素最大值。

2. 第二次遍历,计算其他元素是否满足条件。

暴力破解代码:

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) {
// 不满足条件返回 -1
if (maxIndex != i && nums[maxIndex] < 2 * nums[i])
return -1;
}
return maxIndex;
}
}

思路 2:

简单推理可知,当最大元素是第二大元素的两倍及以上,那么其他的元素自然也符合条件。

所以,我们只需要将,最大元素和第二大元素找出来比较即可。

与思路1相比,思路2只需要计算比较一次。

第二大元素比较代码:

class Solution {
public int dominantIndex(int[] nums) {
int maxIndex = 0;
int second = Integer.MIN_VALUE;
int length = nums.length;

// 最大的元素的索引
for (int i = 1; i < length; i++){
if (nums[i] > nums[maxIndex]){
maxIndex = i;
}
}
// 第二大的元素
for (int i = 0; i < length; i++){
if (i == maxIndex) continue;
if (nums[i] >= second) second = nums[i];
}

if (second == Integer.MIN_VALUE || nums[maxIndex] >= second * 2)
return maxIndex;

return -1;
}
}

评论