算法 : Majority element

Question

我正在为多数元素问题编写一个分而治之的解决方案，如果 n 个整数序列中有一个元素出现超过 n/2 次，则它必须输出 1，否则输出 0。我的代码适用于我能想到的任何测试用例，但评分系统一直说它为测试用例提供了错误的答案。

n = int(input())
array = input().split()
for i in range(n):
    array[i] = int(array[i])
def merge(alist, blist):
    a = len(alist)
    b = len(blist)
    n = a + b
    result = []
    for i in range(n):
        if len(alist) > 0 and len(blist) > 0:
            if alist[0] < blist[0]:
                result.append(alist[0])
                alist.pop(0)
            else:
                result.append(blist[0])
                blist.pop(0)
        elif len(alist) == 0:
            result.extend(blist)
        elif len(blist) == 0:
            result.extend(alist)
    return result
def mergesort(numbers):
    if len(numbers) > 1:
        n = len(numbers)
        alist = numbers[:(n//2)]
        blist = numbers[(n//2):]
        alist = mergesort(alist)
        blist = mergesort(blist)
        numbers = merge(alist, blist)
    return numbers
array = mergesort(array)
key = array[n//2]
count = 0
for i in range(n):
    if array[i] == key:
        count += 1
if count > (n//2):
    print(1)
else:
    print(0)

谁能告诉我代码中的错误？

Answer 1

展开 comment回答:

在merge函数中，当处理一个list被耗尽的情况时，将另一个list添加到合并的末尾list和extend，但是循环没有终止，非空的list没有被清除，所以如果终端extend 出现得早，非空 list 的剩余部分重复多次。将循环更改为以下内容，使用 extend 剩余 list 的终端案例(添加了额外的清理以减少代码长度):

# Stop when first list exhausted, not after fixed repetitions
while alist and blist:
    if alist[0] < blist[0]:
        result.append(alist.pop(0))
    else:
        result.append(blist.pop(0))

# Only one will have contents, simpler to just unconditionally extend,
# rather than test and extend, since extending with empty list is harmless
result += alist
result += blist

旁注:pop(0) 在 list 上是 O(n)，而 .pop() 是 O(1)。对于大型排序，以下内容会更有效:

# Reverse once up front, so you can pop from right, not left
alist.reverse()
blist.reverse()

# Stop when first list exhausted, not after fixed repetitions
while alist and blist:
    if alist[-1] < blist[-1]:
        result.append(alist.pop())
    else:
        result.append(blist.pop())

# Only one will have contents, simpler to just unconditionally extend,
# rather than test and extend, since extending with empty list is harmless
result += alist[::-1]
result += blist[::-1]