day17(力扣)至少是其他数字两倍的最大数(python描述、多解)

谁践踏了优雅 2021-11-05 21:20 146阅读 0赞

题目描述：在一个给定的数组nums中，总是存在一个最大元素 。查找数组中的最大元素是否至少是数组中每个其他数字的两倍。如果是，则返回最大元素的索引，否则返回-1。

示例 1:

输入: nums = [3, 6, 1, 0]
    输出: 1
    解释: 6是最大的整数, 对于数组中的其他整数,
    6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.

示例 2:

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

提示:

nums 的长度范围在[1, 50].
    每个 nums[i] 的整数范围在 [0, 99].

分析：方法一：最值问题小编一般的解决思路就是先将数组排序，这样最值就很直观，我们直接取出，然后再找到数组中元素大于最大数的平方根的那个数的下标（因为某个数字小于最大值的平方根，那么他的 2 倍也会小于最大值，所以就没有必要判断这些数字，他们一定是满足题意的），这样之后我们遍历就只需要从这个下标开始进行向后遍历即可，我们在之后的遍历中采用计数器，如果计数器的数值与我们剩余元素的个数相同的话说明我们的所有元素都符合题意，然后在原数组中找到这个最大值的下标进行返回即可。代码如下：

class Solution:
        def dominantIndex(self, nums: List[int]) -> int:
            import math
            flag = 0        #全局变量
            n = sorted(nums)    #把数组整体进行赋值，方便最后寻找索引
            count = 0           #用来计算是否遍历了数组中剩下的所有元素
            for i in range(len(n)):          #循环找出最大元素的平方根的索引，这样可以减少下一步的索引量
                if n[i] >= math.sqrt(n[len(n) - 1]):
                    flag = i    #后续的测试就从flag对应的下标元素开始
                    break
            for i in range(flag, len(n) - 1):       #判断是否满足题意
                if n[len(n) - 1] > n[i] * 2:
                    count += 1
            if count == len(n) - 1 - flag:      #如果剩下的元素个数等于计数器的值       
                for i in range(len(nums)):          #寻找最大值的下标
                    if nums[i] == n[len(n) - 1]:
                        flag = i
                        return flag
            return -1

方法二：思路与上面的有些相似，我们这次在排序之后找出最后两个元素（也就是最大值和第二大值），来比较第二大值的二倍是不是小于最大值，如果小于，那么我们其他的元素的二倍就一定小于最大值，否则的话就不满足题意。代码如下：

class Solution:
        def dominantIndex(self, nums: List[int]) -> int:
            import math
            #flag = 0        #全局变量
            n = sorted(nums)    #把数组整体进行赋值，方便最后寻找索引
            #count = 0           #用来计算是否遍历了数组中剩下的所有元素
            if len(nums) == 0:
                return -1 
            if len(nums) == 1:
                return 0         
            if n[len(n) - 2] * 2 <= n[len(n) - 1]:
                for i in range(len(nums)):
                    if nums[i] == n[len(n) - 1]:
                        return i
            else:
                return -1

本来小编以为这个方法会得到更快的运行效率，但是小编想多了，他们两个运行效率差不多。本题就是基本的数组遍历、循环，没有什么生僻的知识点，故知识点这一块就不再提及。