我正在努力解决Largest Number At Least Twice of Others - LeetCode
- 最少的人数至少两次
在给定的整数数组
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.
注意:
nums
的长度在[1, 50]
范围内。- 每个
nums[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
运行TestCase:
nums = [1]
my output is : -1 #do not exist such a laregest number
#but the expected is
0
怎么能理解这个Testcase?
我的理解是,如果只有一个元素,没有其他元素,其他元素是无,那么条件:
查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
不满意。
我认为你的理解是正确的。你可以参考这个讨论,他们也对此感到困惑: 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
我会完全修改你的代码并使其更具可读性。 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
您的问题更多是关于逻辑问题而不是编程问题。如果最大值大于列表中的“每隔一个数字”,则问题会要求您给出一个结果,但在该测试中没有其他数字。
在逻辑中,如果要测试的项集合为空,则认为“每个”语句为真。您可以使用all
函数在Python中看到类似的东西,如果其可迭代参数中的“每个”值都是真的,它通常会返回True
。如果你运行all([])
你会得到True
,因为空列表中没有falsey值。
问题可能意味着假设数组中的最大元素至少是数组中其他数字的两倍,直到数组中的一个元素证明了这一点。由于数组中没有其他元素可以反驳,1仍然满足条件,因此输出是其索引而不是-1。
也许这个,在第一个if
和最后一个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