2

我正在努力解决最大数至少是其他数的两倍 - LeetCode

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

在给定的整数数组nums中，总是有一个最大的元素。

找出数组中最大的元素是否至少是数组中其他数字的两倍。

如果是，则返回最大元素的索引，否则返回-1。

示例 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.

示例 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.

笔记：

  1. nums将有一个范围内的长度[1, 50]。
  2. Everynums[i]将是范围内的整数[0, 99]。

条件nums将有一个范围内的长度，[1, 50]不需要检查len(nums) ==1和nums == None

我的解决方案

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        """
        #solution 1
        #1S#############
        G:List[int], 
        F:index
        RQ: largest and at least twice the second         
        #2S#############
        CP:
        RU: largetst >= second * 2 
        #3S##############
        """
        #base case
        if len(nums) == 1: return -1
        lookup = {nums[i]:i for i in range(len(nums))}
        nums.sort()
        first = nums[-1]
        second = nums[-2]
        if first >= second * 2:
            return lookup[first]
        else:
            return -1 #failure 
        #4C########################
        # nums = [1] output = 0

运行测试用例：

nums = [1]
my output is : -1 #do not exist  such a laregest number 
 #but the expected  is 
0

怎么能理解这个Testcase？

我的理解是，如果只有一个元素，没有其他元素，其他元素都没有，所以条件：

找出数组中最大的元素是否至少是数组中其他数字的两倍。

不满意。

4

5 回答 5

2

您的问题更多是关于逻辑问题而不是编程问题。如果最大的大于列表中的“所有其他数字”，则问题要求您给出一个结果，但在该测试中没有其他数字。

在逻辑上，如果要测试的项目集为空，则认为“每个”语句为真。你可以在 Python 中看到类似的函数，如果它的可迭代参数中的“每个”值都是真值all，它通常会返回。True如果你运行all([])你会得到True，因为空列表中没有错误的值。

于 2019-04-19T03:55:33.790 回答
2

我会完全修改您的代码并使其更具可读性。is_twice函数保证返回一个True或False取决于列表中的最大元素是否至少是其他所有元素的两倍。

nums = [1]

def is_twice(lst, max_no):
    return all(max_no >= (2*x) for x in lst if x != max_no)

max_no = max(nums)    
if is_twice(nums, max_no):
    print(nums.index(max_no))  # if you can guarantee there's only one max element else go with below commented code.
    # print([i for i, x in enumerate(nums) if x == max_no])
else:
    print(-1)

# 0
于 2019-04-19T03:43:51.580 回答
1

这个问题可能意味着数组中的最大元素被假定为数组中其他数字的至少两倍，直到数组中的一个元素证明它不是。由于数组中没有其他元素可以证明这一点，因此 1 仍然满足条件，因此输出是它的索引而不是 -1。

于 2019-04-19T03:40:15.420 回答
1

我认为你的理解是正确的。你可以参考这个讨论，他们也对此感到困惑：
https ://leetcode.com/problems/largest-number-at-least-twice-of-others/discuss/176102/Wrong-return-with-1

我想说，您的解决方案效率不高。您的意图是在 中找到最大的两个数字nums，但sort在这里被浪费了，因为您只需要最大的两个数字。所以我认为堆或两个变量在这里更好：

heapq.nlargest(2, nums)
# or find max1, max2 in nums
于 2019-04-19T03:40:44.660 回答
1

if也许这个，在 first和 last有一些变化if：

class Solution:
    def dominantIndex(self, nums) -> int:
        """
        #solution 1
        #1S#############
        G:List[int], 
        F:index
        RQ: largest and at least twice the second         
        #2S#############
        CP:
        RU: largetst >= second * 2 
        #3S##############
        """
        #base case
        if len(nums) == 1: return 0
        lookup = {nums[i]:i for i in range(len(nums))}
        nums.sort()
        first = nums[-1]
        second = nums[-2]
        if first >= second * 2:
            return lookup[first]
        else:
            return -1 #failure 
        #4C########################
        # nums = [1] output = 0

测试用例：

a = Solution()
print(a.dominantIndex([1, 2, 3, 6]))

输出：

3
于 2019-04-19T03:42:46.940 回答