2

我在一个网站 (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] + " ");            
        }
    }
}

非常感谢你的帮助！对此，我真的非常感激！

4

3 回答 3

2

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

完全放弃positives阵列，只需在阵列上循环两次。第一遍打印底片，第二遍打印正片。这仍然2n是O(n)时间和额外的内存O(1)。

于 2013-10-31T18:23:17.100 回答
1

Extra Memory 约束意味着您需要使用的任何额外内存都必须是一个常数因子。也就是说，它需要x字节空间，其中x一些值不取决于输入的大小。

当然，它提到了额外的内存，因为您的数据大小将与其自身成正比，因此它指的是您用于数组本身之外的操作的任何额外（临时？）空间。

在您的解决方案中，您使用的positives是与输入数据成比例的数组。这显然是 O(n) 额外的内存，因此不符合您的限制。

于 2013-10-31T17:47:09.557 回答
0

虽然您可以使用两个循环，但只需摆脱正数组即可。相反，只需使用与第一个循环类似的逻辑

class MyClass {
public static void relative_sort(Integer[] v) {
    for(int i=0; i < v.length; i++){
        if(v[i] < 0)
            System.out.print(v[i] + " ");   
    }
    for(int i=0; i < v.length; i++){
        if(v[i] >= 0)
            System.out.print(v[i] + " ");   
    }

}
}

复杂性是O(N)，你甚至不需要额外的常量内存O(1)

于 2013-10-31T18:34:26.843 回答