具有 O(n) 时间和额外内存 O(1) 的 Java 就地算法

Question

我在一个网站 (talentbuddy.co) 上发现了这个问题，它混淆了我对 Big-O 表示法的所有了解。

这里是问题陈述:

给定一个整数数组，您的任务是将初始数组打印到标准输出 (stdout)，但以特殊方式排序:

所有负数在前并且按照初始数组的相对位置不变 与正整数相同，但它们排在最后。

预期复杂度:O(N)时间，额外内存O(1)

示例输入:-5 2 1 -2 3

示例输出:-5 -2 2 1 3

我知道 O(n) 时间意味着算法运行时间与输入的大小成正比，在这种情况下是数组的大小，但是额外的内存 O(1) 意味着什么？

是否可以使用单个 for 循环来解决这个问题？这就是我的解决方案的样子，我不确定它的运行时间是否为 O(n)。

    import java.util.Arrays;
class MyClass {
    public static void relative_sort(Integer[] v) {
        int[] positives = new int[v.length];
        int counter = 0;
        for(int i=0; i < v.length; i++){
            if(v[i] < 0){
                System.out.print(v[i] + " ");   
            }else{
                 positives[counter] = v[i];  
                 counter++;
            }
        }
        for(int i=0; i < counter; i++){
            System.out.print(positives[i] + " ");            
        }
    }
}

非常感谢您的帮助!非常感谢!

Answer 1

您的解决方案是 O(n) 时间。在最坏的情况下，您遍历数组两次，2n 仍然是 O(n)。但是，你的额外内存也是O(n)，因为positives数组的大小是n，不符合的要求O(1) 额外内存。

完全放弃 positives 数组，简单地遍历数组两次。第一遍打印底片，第二遍打印正片。这仍然是 2n，使其成为 O(n) 时间，额外内存为 O(1)。