使用插入排序查找重复项

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 arrprint(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里面的陈述if

def find_duplicate(arr):

    dup = None  # set this to none to act as flag

    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

            dup = cur

        else:

            arr[j] = cur

    if dup is None:  # check if a duplicate was found

        print("no dupes")

        return arr

    else:

        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]