使用分而治之检查重复项

Question

为了在 nlogn 中搜索重复项，我决定使用经过修改的合并排序。主要问题是出现错误，我不知道如何解决这个问题：结果有时是完全错误的。

我的算法必须 return 如果找到一对（具有相同值的元素）则为 True，如果没有找到一对则为 False。所有这些都必须在分而治之算法内完成。（没有额外的 for 循环 ecc。）

这是代码

def check_duplicates(X):   
    if len(X)>1:
        mid = len(X)//2
        lefthalf = X[:mid]
        righthalf = X[mid:]

        check_duplicates(lefthalf)
        check_duplicates(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i] == righthalf[j]:
                return True

            if lefthalf[i]<righthalf[j]:
                X[k]=lefthalf[i]
                i=i+1
            else:
                X[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            X[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            X[k]=righthalf[j]
            j=j+1
            k=k+1

   return False

让我们举几个例子：让X=[1,2,3]函数returnsfalse，就可以了。让X=[1,3,2]函数returnsfalse也可以

主要问题出在这种情况下：

让X=[1,3,3]函数returns false，这是错误的（应该return正确）。

让X=[4,6,6]函数returns false，这是错误的等等。

主要问题是当我将两个相同的值放在列表末尾时，我不知道如何解决...

ps: 我为我的英语道歉

Answer 1

你忘记了，如果你进行递归调用，并且调用结果为 True，也为 return True：因此，将递归调用修改为：

if(check_duplicates(lefthalf)) :
    return True

或完整（缩进）版本如下：

def check_duplicates(X):   
    if len(X)>1:
        mid = len(X)//2
        lefthalf = X[:mid]
        righthalf = X[mid:]
        if(check_duplicates(lefthalf)) :
            return True
        if(check_duplicates(righthalf)) :
            return True
        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf) :
            if lefthalf[i] == righthalf[j]:
                return True
            if lefthalf[i]<righthalf[j]:
                X[k]=lefthalf[i]
                i=i+1
            else:
                X[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            X[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            X[k]=righthalf[j]
            j=j+1
            k=k+1

    return False

在 while 循环中，您只检查交叉相等性（两个子列表中的相等元素）。但是如果在顶级比较中 return Trues，则您的版本中的结果仅 returned。

换句话说，您忘记在调用堆栈中传播 True 值。

使用分而治之检查重复项

Checking duplicates with divide and conquer

algorithm

mergesort

divide-and-conquer

python-3.x