通过移动元素删除重复项的复杂性

Question

以下代码试图通过覆盖重复元素来从排序数组中删除重复项。虽然嵌套了for循环，但复杂度绝对小于O(n^2)。以下代码的复杂度是多少？

    int n = arr.length;
    for(int i=0;i<n;i++){

        if(arr[i]==arr[i+1]){
            for(int j=i+1;j<n-1;j++){
                arr[j]=arr[j+1];
            }
            n--; i--; 
        }   
    }

Answer 1

让我们从第一位开始。它肯定不是重复的，所以你不做任何移动。然后我们移动到第二个位置。它可以从第一个位置值重复，然后可能不是。如果是，那么你必须将它移动到末尾，因此，对于前两个位置，你有两种情况，一种只是移动数组（它不是重复的），第二种是将元素移动到数组的末尾，这需要 arr[j]=arr[j+1].

的 n-2 操作

现在，如果我们将第三个值移到第二个位置，我们仍然在上面（i-- 部分）。它可以是第一个值的副本，也可能不是。对于第一个选项，你必须进行 n-3（因为你做了 n--，所以你将它从位置 2 移动到位置 n-1）arr[j]=arr[j+1] 的操作。现在，如果第二个值不是第一个值的副本（所以你没有做 i-- 和 n--），但第三个值是前两个值之一的副本，你仍然必须做 [= arr[j]=arr[j+1] 的 14=] 操作（从位置 3 到位置 n）。因此，每种情况下的操作数都保持不变。

所以，我们这里有一个模式：n-2 + n-3 + n -4 + ... + 3 + 2 + 1 移动东西。这个总和是：

n-2 + n-3 + n -4 + ... + 3 + 2 + 1 = n(n+1)/2 - n - n + 1

所以基于此，由于第一部分是遍历数组，即O(n)，该算法的复杂度为O(n^2)。最坏的情况是数组中有所有相同的值。

现在，有更好的方法了。将所有值放在 Set 中。这需要遍历数组 (O(n))，并检查 Set 中是否有内容，即 O(1)。然后从Set中取出所有结果，并将它们放入数组中，即O(n)。所以，这种算法的复杂度是O(n).

通过移动元素删除重复项的复杂性

Complexity of removing duplicates by shifting elements

big-o

time-complexity