众数 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, right)。相反，他们应该越过范围（左，右）。从 0 开始可能，并且会导致在较小的子问题中返回不正确的主要元素。

此外，除了 for 循环覆盖范围内起始索引不正确的问题，您的递归调用参数似乎也有问题，这可能是由于您的直觉导致您忽略了一些细节。在整个 get_majority_element 函数中，您将参数 right 视为不在列表中的第一个索引，而不是 right列表中最右边元素的索引。

但是，在您的第一个递归调用中，您给出的第三个参数就好像它是该列表中包含的最后一个元素一样。如果 right 是不在该列表中的第一个元素的索引，它实际上应该与您在下一行中进行的第二个递归调用的第二个参数相同。所以，你进行的第一个递归调用的第三个参数比它应该的少 1，导致你每次递归向下时忽略 1 个元素。

第三，您在 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 算法在列表中查找多数元素。我正在使用一个内置函数，计数；因此，如果多数元素大于列表大小的一半，则输出为 1，否则为 0。您可以在此 link 中找到更多关于 Boyers 和 Moore 算法寻找多数的信息 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))

众数 Python

Majority Element Python

python

algorithm

divide-and-conquer

python-3.x