使用分而治之的多数元素

Question

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

我在 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)

有众数时结果正确，没有众数时return结果错误

我尝试将 return 语句更改为：

    if left_count > right_count:
        return left
    elif left_count < right_count:
        return right
    else:
        return -1

所以当没有正确答案时它returns -1。当输入为 [1,2,1,3] 时，结果为 -1（正确答案），但当输入为 [1,2,3,3] 时，输出为 3，这是错误的。

似乎每个人都在使用这个解决方案，但它不起作用。关于如何修复它有什么想法吗？

TIA

Answer 1

我认为递归步骤是可以的，因为如果有多数元素，它必须是数组至少一半的多数元素，并且递归步骤会找到它。如果没有多数元素，递归算法仍将 return 一个（错误的）候选者。

如果你想让程序检测元素是否确实是多数元素，我只想更改最后一步。

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

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

使用分而治之的多数元素

Majority element using divide&conquer

python

divide-and-conquer

python-3.x