algorithm - 使用分而治之检查重复项

Question

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

如果找到一对(具有相同值的元素)，我的算法必须返回 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]函数返回false，就ok了。让X=[1,3,2]函数返回false，这也是可以的。

主要问题在于这种情况:

让X=[1,3,3]函数返回false，这是错误的(应该返回true)。

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

主要问题是当我在列表末尾放置两个相同的值时，我不知道如何修复它...

ps:我为我的英语道歉

Answer 1

您忘记了，如果您执行递归调用，并且调用结果为 True，则返回 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 循环中，您只检查交叉相等性(两个子列表中的元素相等)。但是只有在顶层比较中 返回 True 时，您的版本中的结果才会返回。

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