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

Posted on | In
Words count in article: 553 | Reading time ≈ 2

题目

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

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

示例1：

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

示例2：

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

示例3：

1
2
3
输入：nums = [1]
输出：0
解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。

提示：

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

解法：

解法一：

暴力

先找出最大的数值，挨个判断是否是剩下的两倍大。

需要注意的是要在比较的时候要排除自身。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int dominantIndex(int[] nums) {
		int max = Integer.MIN_VALUE;
		int bigIndex = -1;
		for (int i = 0;i < nums.length;i++) {
			if (max < nums[i]) {
				max = nums[i];
				bigIndex = i;
			}
		}
		
		for (int i = 0;i < nums.length;i++) {
			if (i == bigIndex) {
				continue;
			}
			if (nums[i] * 2 > max) {
				return -1;
			}
		}
		return bigIndex;
    }

解法二：

遍历一次

在遍历的时候选出最大值和第二大的值，判断最大值是否是第二大值的两倍。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int dominantIndex(int[] nums) {
		if (nums.length == 1) {
			return 0;
		}
		
		int first = Integer.MIN_VALUE;
		int second = Integer.MIN_VALUE;
		int bigIndex = -1;
		for (int i = 0;i < nums.length;i++) {
			int n = nums[i];
			if (n > first) {
				second = first;
				first = n;
				bigIndex = i;
			} else if (n > second) {
                second = n;
            }
		}
		return second * 2 > first ? -1 : bigIndex;
	}

解法三：

遍历一次

在遍历的时候直接判断最大值是否满足要求

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int dominantIndex(int[] nums) {
		int max = 0;
		boolean pin = true;
		for (int i = 1; i < nums.length; i++) {
			if (nums[max] < nums[i]) {
				if (nums[i] >= nums[max] * 2) {
					pin = true;
				} else {
					pin = false;
				}
				max = i;
			} else {
				if (nums[max] < nums[i] * 2) {
					pin = false;
				}
			}
		}
		if (pin) {
			return max;
		} else {
			return -1;
		}
	}
0%