题目

给一个整数数组,该数组肯定存在一个最大值。

找到这个最大值并且确认这个最大值是否是其他值的至少2倍大。如果是,返回这个最大值的下标位置,如果不是,返回-1。

Example 1:

Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6是一个最大值,对于其他数字来说,都比他们至少大2倍。而6的位置是1,所以返回1。

Example 2:

Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4虽然是最大值,但是对于数字3来说,没有大于3倍。因此返回-1。

Note:

  1. 该数组的长度在1-50之间
  2. 对于每一个下标的值,都在0-99之间

思路

其实比较简单,就是找到这个最大值,然后记录这个最大值的位置,然后再遍历查看是否至少是其他值的两倍,于是我们可以快速写出下面的代码:

func dominantIndex(nums []int) int {
    // find the max
    maxIndex := -1
    for k, v := range nums {
        if v >= nums[maxIndex] {
            maxIndex = k
            continue
        }
    }
    if maxIndex > -1 {
        for k, v := range nums {
            if maxIndex == k {
                continue
            }

            if v*2 > nums[maxIndex] {
                return -1
            }
        }
    }

    return maxIndex
}

但是我们其实可以发现,第二个循环里有些不必要,为什么呢?因为只要发现,只要这个最大值比第二大的值至少大2倍,对于其他值来说,肯定也是大于2倍的,那么我们只要找到最大和第二大的值,然后看最大值比第二大的值大多少倍即可。

func dominantIndex2(nums []int) int {
    if len(nums) < 2 {
        return 0
    }
    largest, second := 0, 1

    if nums[largest] < nums[second] {
        largest, second = 1, 0
    }

    for i := 2; i < len(nums); i++ {
        if nums[i] > nums[largest] {
            largest, second = i, largest
        } else if nums[i] > nums[second] {
            second = i
        }
    }

    if nums[second]*2 <= nums[largest] {
        return largest
    }

    return -1
}

详细代码见: https://github.com/scofieldpeng/leetcode/blob/master/dominantIndex/dominantIndex.go

原题目见: https://leetcode.com/problems/largest-number-at-least-twice-of-others/