使用分而治之的多数元素

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语句更改为：

    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，这是错误的。

似乎每个人都使用此解决方案，但是它不起作用。关于如何解决它的任何想法？

TIA

Answer 1

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

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

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

with

majority = ((hi - lo) + 1) / 2
if left_count > majority:
     return left
if right_count > majority:
     return right
return -1

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