使用插入排序查找重复项

Question

def find_duplicate(arr):

    for i in range(1, len(arr)):

        cur = arr[i]

        j = i

        while j > 0 and arr[j - 1] > cur:

            arr[j] = arr[j - 1]

            j -= 1

        arr[j] = cur

        if arr[j-1] == cur:

            arr[j] = cur

            return f"This is the duplicate {cur}, {arr}"

        else:

            arr[j] = cur

    print("no dupes")

    return arr

print(find_duplicate([1,-5,3,4,-10,100,250,-325,100]))

当我在数组末尾添加 100 时，它会被排序，重复值显示为 100 并且数组已正确排序，但是当我在末尾添加负数（例如 -5）作为重复值时，它不会排序-5 但有些人如何理解这个数字是重复的。我究竟做错了什么？

请查看我提到的两个数组作为输入：

arr = [1,-5,3,4,-10,100,250,-325,100] <- 100 结束

arr = [1,-5,3,4,-10,100,250,-325,-5] <- -5 结束

print(find_duplicate([1,-5,3,4,-10,100,250,-325,100]))

print(find_duplicate([1,-5,3,4,-10,100,250,-325,-5]))

# OUTPUT BELOW:

This is the duplicate 100, [-325, -10, -5, 1, 3, 4, 100, 100, 250]

This is the duplicate -5, [-5, 1, 3, 4, -10, 100, 250, -325, -5]

更新：

当再次运行这个时

print(find_duplicate([1,-5,3,4,-10,100,250,-325,-5,10]))

this is the duplicate -5, [-325, -10, -5, -5, 1, 3, 4, 100, 250, 10]

似乎它只是不断附加数字，而不是在找到重复项后对它们进行排序

Answer 1

你的逻辑是正确的，除了return里面的陈述ifdef find_duplicate(arr):&nbsp; &nbsp; dup = None&nbsp; # set this to none to act as flag&nbsp; &nbsp; for i in range(1, len(arr)):&nbsp; &nbsp; &nbsp; &nbsp; cur = arr[i]&nbsp; &nbsp; &nbsp; &nbsp; j = i&nbsp; &nbsp; &nbsp; &nbsp; while j > 0 and arr[j - 1] > cur:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[j] = arr[j - 1]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j -= 1&nbsp; &nbsp; &nbsp; &nbsp; arr[j] = cur&nbsp; &nbsp; &nbsp; &nbsp; if arr[j-1] == cur:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[j] = cur&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dup = cur&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[j] = cur&nbsp; &nbsp; if dup is None:&nbsp; # check if a duplicate was found&nbsp; &nbsp; &nbsp; &nbsp; print("no dupes")&nbsp; &nbsp; &nbsp; &nbsp; return arr&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; return f"This is the duplicate {dup}, {arr}"print(find_duplicate([1,-5,3,4,-10,100,250,-325,-5]))print(find_duplicate([1,-5,3,4,-10,100,250,-325,100]))print(find_duplicate([1,-5,3,4,-10,100,250,-325,-5,10]))输出This is the duplicate -5, [-325, -10, -5, -5, 1, 3, 4, 100, 250]This is the duplicate 100, [-325, -10, -5, 1, 3, 4, 100, 100, 250]This is the duplicate -5, [-325, -10, -5, -5, 1, 3, 4, 10, 100, 250]