首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >使用分而治之的多数元素

问使用分而治之的多数元素
EN

Stack Overflow用户
提问于 2020-02-17 03:05:16
回答 1查看 267关注 0票数 0

我想使用分治算法从列表中找到大多数元素。

我在Leetcode上看到了这个解决方案的代码:

代码语言:javascript
复制
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)

当有多数元素时,结果是正确的,但当没有这样的元素时,它返回错误的结果。

我尝试将返回语句更改为:

代码语言:javascript
复制
    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,这是错误的。

似乎每个人都在使用这个解决方案,但它并不起作用。有没有关于如何修复它的想法?

提亚

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-02-17 04:56:45

我认为递归步骤是可以的,因为如果有多数元素,它必须是数组中至少一半的多数元素,并且递归步骤会找到它。如果没有多数元素,递归算法仍然会返回一个(错误的)候选。

如果您希望程序检测该元素是否确实是多数元素,我只需更改最后一步。

代码语言:javascript
复制
def majorityElement(self, nums):
    ...
    candidate = majority_element_rec(0, len(nums)-1)
    if nums.count(candidate) > len(nums)//2:
        return count
    else:
        return -1

或者,递归步骤可以通过替换最后一行来执行相同的检查找到的候选元素是否确实是多数元素:

代码语言:javascript
复制
return left if left_count > right_count else right

使用

代码语言:javascript
复制
majority = ((hi - lo) + 1) / 2
if left_count > majority:
     return left
if right_count > majority:
     return right
return -1

这应该仍然有效,因为多数元素(如果存在)必须递归地成为数组的一半中的多数元素,因此必须仍然传播。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/60252147

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档