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

Question

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

下面我介绍我的解决方案。

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

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

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

你能在没有额外空间和 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) 算法。

• 考虑如何将一组数字表示为位图。
• 考虑“时钟耐心”纸牌游戏 ( https://en.wikipedia.org/wiki/Clock_Patience )

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