Элемент большинства, использующий разделяй и властвуй

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)

, когда существует элемент большинства результат правильный, но когда такого элемента нет, он возвращает неверный результат.

Я попытался изменить оператор возврата на:

    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

на

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

Это все равно должно работать, потому что мажоритарный элемент, если он существует, должен рекурсивно быть мажоритарным элементом в одной половине массива и, таким образом, все еще распространяться.