j

jaryue

V1

2023/05/13阅读:11主题:默认主题

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

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


题目描述

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

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

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

示例 1:

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

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

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

提示:

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

解题思路

方法1:模拟+遍历
根据题意,我们需要找出最大的数与第二大的数并且判断最大的数比第二大的数的两倍还要大

  1. 找出最大的数与第二大的数
  2. 判断是否满足输出条件,如果满足,输出该数的位置,不满足输出-1

法1

  • 时间复杂度(O(n))
  • 空间复杂度(O(1))

执行结果

两个索引变量,maxIndex表示最大元素的索引,secondMaxIndex表示第二大元素的索引。

我们遍历数组并更新这两个索引,然后在最后检查最大元素是否至少是第二大元素的两倍,以确定返回的结果。

法1

func dominantIndex(nums []int) int {
    maxIndex := 0
    secondMaxIndex := -1

    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[maxIndex] {
            secondMaxIndex = maxIndex
            maxIndex = i
        } else if secondMaxIndex == -1 || nums[i] > nums[secondMaxIndex] {
            secondMaxIndex = i
        }
    }

    if nums[maxIndex] >= 2*nums[secondMaxIndex] {
        return maxIndex
    }

    return -1
}

执行结果: 通过 显示详情 查看示例代码 添加备注

执行用时: 4 ms , 在所有 Go 提交中击败了 32.39% 的用户 内存消耗: 2 MB , 在所有 Go 提交中击败了 83.10% 的用户 通过测试用例: 231 / 231 炫耀一下:

法2


法3


分类:

后端

标签:

后端

作者介绍

j
jaryue
V1