Leetcode 刷题笔记 (4)

题目描述

• In a given integer array nums, there is always exactly one largest element.
• Find whether the largest element in the array is at least twice as much as every other number in the array.
• If it is, return the index of the largest element, otherwise return -1.

Example 1:

Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than 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 isn't at least as big as twice the value of 3, so we return -1.

Note:

1. nums will have a length in the range [1, 50].
2. Every nums[i] will be an integer in the range [0, 99].

解题思路

此题目要求我们找出这个数组的 最大值 ，同时要求判断这个 最大值 是否满足 至少是数组中每个其他数字的两倍 的条件，如果满足，则返回最大元素的索引，否则返回-1。

1. 遍历一遍数组 nums，找出最大的数字 max 以及它对应的下标 index 并记录下来。
2. 重新遍历数组，如果我们找到数组中有元素满足 i != index 且 2 * nums[i] > max ，则返回 -1 ，否则，我们返回 index。

参考代码

//C++
class Solution {
public:
	int dominantIndex(vector<int>& nums) 
	{
		int max = nums[0], index = 0;
		for (int i = 1; i < nums.size(); i++)
		{
			if (max < nums[i])
			{
				max = nums[i];
				index = i;
			}
		}
		for (int i = 0; i < nums.size(); i++)
		{
			if (max < nums[i] * 2 && i != index)
				return -1;
		}
		return index;
	}
};

本文由 机灵鹤 SmartCrane 创作
本站文章所有原创文章, 转载前请务必署名
最后编辑时间为: 2018-09-19 22:40