我想使用分治算法从列表中找到大多数元素。
我在Leetcode上看到了这个解决方案的代码:
class Solution:
def majorityElement(self, nums, lo=0, hi=None):
def majority_element_rec(lo, hi):
# base case; the only element in an array of size 1 is the majority
# element.
if lo == hi:
return nums[lo]
# recurse on left and right halves of this slice.
mid = (hi-lo)//2 + lo
left = majority_element_rec(lo, mid)
right = majority_element_rec(mid+1, hi)
# if the two halves agree on the majority element, return it.
if left == right:
return left
# otherwise, count each element and return the "winner".
left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)
right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)
return left if left_count > right_count else right
return majority_element_rec(0, len(nums)-1)当有多数元素时,结果是正确的,但当没有这样的元素时,它返回错误的结果。
我尝试将返回语句更改为:
if left_count > right_count:
return left
elif left_count < right_count:
return right
else:
return -1因此,当没有正确答案时,它返回-1。当输入为[1,2,1,3]时,结果为-1(正确答案),但当输入为[1,2,3,3]时,输出为3,这是错误的。
似乎每个人都在使用这个解决方案,但它并不起作用。有没有关于如何修复它的想法?
提亚
发布于 2020-02-17 04:56:45
我认为递归步骤是可以的,因为如果有多数元素,它必须是数组中至少一半的多数元素,并且递归步骤会找到它。如果没有多数元素,递归算法仍然会返回一个(错误的)候选。
如果您希望程序检测该元素是否确实是多数元素,我只需更改最后一步。
def majorityElement(self, nums):
...
candidate = majority_element_rec(0, len(nums)-1)
if nums.count(candidate) > len(nums)//2:
return count
else:
return -1或者,递归步骤可以通过替换最后一行来执行相同的检查找到的候选元素是否确实是多数元素:
return left if left_count > right_count else right使用
majority = ((hi - lo) + 1) / 2
if left_count > majority:
return left
if right_count > majority:
return right
return -1这应该仍然有效,因为多数元素(如果存在)必须递归地成为数组的一半中的多数元素,因此必须仍然传播。
https://stackoverflow.com/questions/60252147
复制相似问题