マジョリティ要素Python

Question

Python 3では、 "Majority Element"の分割と征服アルゴリズムの実装に適切な出力が得られません。

これは比較的正確です。しかし、それはまだ私が何かを欠いているように見えるか、それは少しオフであり、私はそれがなぜあるのか理解できません。

私はいくつかのデバッグステートメントとさまざまなことを試しました。これは、コードの上の注釈に記載されている特定のケースのように見えます。再帰呼び出しを行うときは、 "left_m"は-1、 "right_m"は941795895が解決されます。各インデックスの要素をそれらの変数と比較すると、明らかにカウンタは増分しません。

私はこれについて間違った方法をしていますか？どんな助けでも大歓迎です。

ありがとうございました。

# 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関数全体で、の右のをリストにない最初のインデックスとし、の右のをリストの最も右の要素のインデックスとします。

ただし、最初の再帰呼び出しでは、最後の要素がで、そのリストにが含まれているかのように、3番目の引数を指定します。 rightがそのリストにない最初の要素のインデックスである場合、次の行に2番目の再帰呼び出しの2番目のパラメータと実際に同じである必要があります。したがって、最初の再帰呼び出しの3番目の引数は1より小さく、再帰的にになるたびに1要素を見落とします。

第3に、forループの後のif文にエラーがあります。これはループ範囲の問題と同様です。すべての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

BoyersとMooreのアルゴリズムを使用して、リストの中の多数の要素を見つけようとしています。私はinbuilt関数を使用しています。そう、大多数の要素がリストの半分のサイズよりも大きい場合、それは1の出力を与え、そうでない場合は0あなたがなぜ正しいだろう大半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))