LeetCode算法题-Largest Number At Least Twice of Others(Java)
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第177题（顺位题号是747）。在给定的整数数组中，总有一个最大的元素。查找数组中的最大元素是否至少是数组中每个其他数字的两倍。如果是，则返回最大元素的索引，否则返回-1。例如：
输入：nums = [3,6,1,0]
输出：1
说明：6是最大的整数，对于数组x中的每个其他数字，6是x的两倍多。 值6的索引是1，所以我们返回1。
输入：nums = [1,2,3,4]
输出：-1
说明：4至少不是3的值的两倍，所以我们返回-1。
注意：
- nums的长度在[1,50]范围内。
- 每个nums [i]将是[0,99]范围内的整数。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
题目的要求是返回最大数的索引，所以需要先将最大数找出来，并记录下其索引。然后在次遍历数组中的元素，将最大数之外的其他数都乘以2和最大数比较(在此处我是使用位移处理)，如果大于就返回-1，如果其他元素都满足条件，就返回之前记录的最大数的索引。
public int dominantIndex(int[] nums) {
int index = 0, max = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
index = i;
}
}
for (int i=0; i<nums.length; i++) {
if (nums[i] != max && nums[i]<<1 > max) {
return -1;
}
}
return index;
}
03 第二种解法
我们还可以只使用一次循环来解决。并非需要使用每一个元素乘以2后再去和最大元素比较，只需要用第二大的数去比较就行，如果第二大的数不能满足条件，就可以直接做判断了。比如[2,3,4]，3乘以2等于6大于4，不符合题目要求，就不需要比较2了。
public int dominantIndex(int[] nums) {
int max = 0, second = 0, index = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] > max) {
second = max;
max = nums[i];
index = i;
} else if(nums[i] > second) {
second = nums[i];
}
}
return second<<1 <= max ? index : -1;
}
04 小结
算法专题目前已日更超过五个月，算法题文章177+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
