Большинство элементов Python

Question

У меня возникли проблемы с получением правильного вывода на мой разрыв «большинство элементов» и властвуй реализацию алгоритма в Python 3.

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

Я пробовал некоторое отладочное заявление и разные вещи. Похоже, что в конкретном случае, указанном в комментарии выше кода, он разрешает -1 для «left_m» и 941795895 для «right_m», когда он выполняет рекурсивные вызовы. Когда он сравнивает элемент по каждому индексу с этими переменными, счетчик, очевидно, никогда не будет увеличиваться.

Я иду об этом неправильно? Любая помощь будет принята с благодарностью.

Спасибо.

# Input: 
# 10 
# 2 124554847 2 941795895 2 2 2 2 792755190 756617003 
# Your output: 
# 0 
# 
# Correct output: 
# 1 

def get_majority_element(a, left, right): 
if left == right: 
    return -1 
if left + 1 == right: 
    return a[left] 

left_m = get_majority_element(a, left, (left + right - 1)//2) 
right_m = get_majority_element(a, (left + right - 1)//2 + 1, right) 

left_count = 0 
for i in range(0, right): 
    if a[i] == left_m: 
     left_count += 1 
if left_count > len(a)//2: 
    return left_m 

right_count = 0 
for i in range(0, right): 
    if a[i] == right_m: 
     right_count += 1 
if right_count > len(a)//2: 
    return right_m 

return -1 

if __name__ == '__main__': 
    input = sys.stdin.read() 
    n, *a = list(map(int, input.split())) 
    if get_majority_element(a, 0, n) != -1: 
     print(1) 
    else: 
     print(0) 

Answer 1

При подсчете появление левых и правых основных элементов, ваши петли идут в диапазоне (0, справа). Вместо этого они должны перемещаться по диапазону (слева, справа). Начиная с 0 может и приведет к возврату неправильных основных элементов в меньшие подзадачи.

Кроме того, помимо проблемы с неправильными начальными индексами в диапазонах, на которые распространяется ваша петля, у вас, похоже, проблема с аргументами рекурсивного вызова, возможно, из-за вашей интуиции, заставляющей вас упускать некоторые детали. Во всей функции get_majority_element вы обрабатываете параметр справа, чтобы быть первым индексом, которого нет в списке, в отличие от справа является индексом самого правого элемента в списке.

Однако в первом рекурсивном вызове вы указываете третий аргумент, как если бы последний элемент включил в этот список. Если right является индексом первого элемента, не входящего в этот список, он должен фактически совпадать со вторым параметром второго рекурсивного вызова, который вы делаете в следующей строке. Итак, третий аргумент первого рекурсивного вызова, который вы делаете, меньше, чем должно быть на 1, заставляя вас пропускать 1 элемент каждый раз, когда вы рекурсивно опускаетесь.

В-третьих, вы имеете ошибку в операторах if, следующих за циклами for, аналогично проблеме, которую вы имели с диапазонами петель. Вы делите элементы элемента для всех элементов len (a), хотя вам нужно только заботиться о подзадачи, в которой вы сейчас работаете. Итак, вы должны разделить его на количество элементов в этой подзадаче, а не на len (a). (т. е. (справа - слева) // 2)

Ниже приведен рабочий код и посмотрите here, чтобы наблюдать за его исполнением.

def get_majority_element(a, left, right): 
    if left == right: 
     return -1 
    if left + 1 == right: 
     return a[left] 

    left_m = get_majority_element(a, left, (left + right - 1)//2 + 1) 
    right_m = get_majority_element(a, (left + right - 1)//2 + 1, right) 
    left_count = 0 
    for i in range(left, right): 
     if a[i] == left_m: 
      left_count += 1 
    if left_count > (right-left)//2: 
     return left_m 

    right_count = 0 
    for i in range(left, right): 
     if a[i] == right_m: 
      right_count += 1 
    if right_count > (right-left)//2: 
     return right_m 

    return -1 

if __name__ == '__main__': 
    input = sys.stdin.read() 
    n, *a = list(map(int, input.split())) 
    print("n=" + str(n)) 
    if get_majority_element(a, 0, len(a)) != -1: 
     print(1) 
    else: 
     print(0) 

Answer 2

Я пытаюсь использовать алгоритм Бойерса и Мура, чтобы найти элемент большинства среди списка. Я использую встроенную функцию, count; поэтому, если элемент большинства больше половины размера списка, то он дает выход 1, иначе 0. Вы можете найти больше в этой связи о Boyers и алгоритме Мура на поиск большинства Algorithm information here

# Uses python3 
import sys 

def get_majority_element(a,n): 
    maximum = a[0] 
    amount = 1 
    for i in (a[1:]): 
     if not maximum == i: 
      if amount >= 1: 
       amount = amount - 1 
      else: 
       maximum = i 
       amount = 1 
     else: 
      amount = amount + 1 
    output = a.count(maximum) 
    if output > n//2: 
     return 1 
    return 0 



if __name__ == '__main__': 
    input = sys.stdin.read() 
    n, *a = list(map(int, input.split())) 
    print (get_majority_element(a,n))