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 +篇，公众号对话框回复【 数据结构与算法 】、【 算法 】、【 数据结构 】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！