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

Я хочу найти элемент большинства из списка, используя алгоритм «разделяй и властвуй».

Я видел этот код на 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, что неверно.

Кажется, что все используют это решение, но оно не работает. Любые идеи о том, как это исправить?

ТИА


python-3.x python divide-and-conquer
person Roy Ancri    schedule 16.02.2020    source источник
comment
Обратите внимание, что в спецификации задачи говорится, что вы можете предположить, что массив не пуст. и мажоритарный элемент всегда существует в массиве. Вы правы, что этот алгоритм не будет работать, если нет мажоритарного элемента.   -  person PaulR    schedule 16.02.2020
comment
Я, вероятно, пропустил это, есть идеи, как изменить его, чтобы он возвращал -1, когда нет мажоритарного элемента?   -  person Roy Ancri    schedule 16.02.2020

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, что рекурсивный шаг в порядке, поскольку, если есть мажоритарный элемент, он должен быть мажоритарным элементом хотя бы одной из половин массива, и рекурсивный шаг найдет его. Если нет мажоритарного элемента, рекурсивный алгоритм все равно вернет (неправильного) кандидата.

Если вы хотите, чтобы программа определяла, действительно ли элемент является мажоритарным, я бы просто изменил последний шаг.

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

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

person PaulR    schedule 16.02.2020
comment
Я думал сделать что-то подобное, но боюсь, что это больше не считается алгоритмом «разделяй и властвуй», потому что вы вручную проверили последний пункт. - person Roy Ancri; 17.02.2020
comment
@RoyAncri похоже, что подпрограмма основной функции - разделяй и властвуй - person Piggy Wenzhou; 09.08.2020