查找数组中消失的所有数字的大 O 时间复杂度

Question

当时我正在解决这个代码练习。我不知道我当前的解决方案是否仍在 O(n) 运行时上。

下面我给出我的解决方案。

找出数组中所有消失的数字

给出一个整数数组，其中 1 <= a[i] <= n（n = 数组大小），一些元素出现两次，其他元素出现一次。

找出[1, n]中所有没有出现在这个数组中的元素

你能在没有额外 space 且运行时间为 O(n) 的情况下完成吗？

示例：

输入： [4、3、2、7、8、2、3、1]

输出： [5, 6]

public static void main(String[] args) {
    findAllNumbersDisappeared(new int[] { 4,3,2,7,8,2,3,1});
}

/* the idea is that since we have a size _n_ array and it has numbers from 1 to n, 
 * given that are repeated numbers, we can iterate over the array and 
 * keep placing the elements in the position equal to their value 
 * (i.e. 1 is placed in the first position, 2 in the second, 3 in the third, and so on)
 * Once that is done by swapping the elements, we iterate over the array again and 
 * compare the position with the value at that position. 
 * 
 * For the positions where they don't match, 
 * it means that whereas it should ideally have had the same value at that position (if there were no repeats), 
 * that positional value represents the missing number.
 * */
public static void findAllNumbersDisappeared(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        while (arr[i] != (i+1) && arr[i] != arr[arr[i]-1]) {
            swap(arr, i, arr[i]-1);
        }
    }

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != (i+1)) {
            System.out.println(i+1);
        }
    }
}

private static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

可能我对大 O 理论感到困惑。第一个循环在N项上迭代（其中N是数组的长度，所以这是O（n）），内部while在整个程序流程中没有执行超过N次。

我不认为这个程序是 O(n^2)，我认为是在 O(n) 和 O(n log n) 之间。你能支持我确定这个解决方案的正确时间复杂度吗？

Answer 1

你的解是O(N)，但我认为不正确。（测试一下！）

提示：有一个真正解决问题的O(N)算法。

考虑如何将一组数字表示为位图。
考虑 "clock patience" 纸牌游戏 (https://en.wikipedia.org/wiki/Clock_Patience)

（这些提示旨在让您朝着正确的方向思考。我认为您可能大部分时间都在那里，但我希望您找到适合自己的正确解决方案。为了最大限度地提高学习/自信-建筑。）

查找数组中消失的所有数字的大 O 时间复杂度

Big O Time complexity for Find All Numbers Disappeared in an Array

java

arrays

algorithm

big-o

time-complexity