1

我正在处理一项任务，但有些问题没有得到答案。

我被问到：

输入：一个长度为 N 的数组 A，它只能包含从 1 到 N 的整数

输出：TRUE - A 包含重复，FALSE - 否则。

我创建了一个通过我的测试用例的类。

public class ArrayOfIntegers {


public boolean isArrayContainsDuplicates(int [] intArray){
    
    int arraySize = intArray.length;
    
    long expectedOutPut = arraySize*(arraySize+1)/2;
            
    long actualOutput = 0;
    
    for(int i =0 ; i< arraySize; i++){
        
        actualOutput =  actualOutput + intArray[i];
        
    }
            
    if(expectedOutPut == actualOutput)
        return false;
    
    return true;
}   

}

现在对此有进一步的问题

  1. 是否可以提供答案而不破坏输入数组 A？

    我还没有销毁数组。那么我所做的是否正确？

  2. 分析算法的时间和空间复杂度？

    所以我需要写一些关于 for 循环的东西，一旦我找到重复的元素，我就应该打破循环。坦率地说，我对时间和空间复杂度的概念不是很清楚。

  3. 时间和空间都可能是 O(n) 吗？

    这应该是否，因为 n 可以是任何数字。同样，我对 O(n) 不是很清楚。

谢谢

4

5 回答 5

2

是否可以提供答案而不破坏输入数组 A？

是的。例如，如果您不关心它所花费的时间，您可以为每个可能的数字循环一次数组，并检查您是否只看到一次（如果没有，则必须有重复）。那将是O（N ^ 2）。

通常，您会使用额外的数组（或其他数据结构）作为临时列表（这也不会破坏输入数组，请参见下面的第三个问题）。

分析算法的时间和空间复杂度？

您的算法在 O(n) 中运行，只对输入数组进行一次传递，并且不需要额外的空间。但是，它不起作用。

时间和空间都可能是 O(n) 吗？

是的。

有另一个相同大小的数组（大小= N），在那里计算你看到每个数字的频率（单次通过输入），然后检查计数（单次通过输出，或者当你有错误时短路）。

所以我需要写一些关于 for 循环的东西，一旦我找到重复的元素，我就应该打破循环。

不。复杂性考虑总是关于最坏的情况（或者有时是平均情况）。在最坏的情况下，您无法跳出循环。在一般情况下，你可以在循环的一半后突破。无论哪种方式，虽然对于等待实际实现以完成计算的人来说很重要，但这对可伸缩性没有影响（复杂性随着 N 无限增长）。不考虑恒定的偏移量和乘数（例如早期突破的 50%）。

于 2012-06-20T23:05:13.803 回答
0

作为提示：

  1. 是的，可以提供答案而不破坏阵列。您的代码*提供了一个示例。

  2. 时间复杂度可以看作是“这个算法做了多少有意义的操作？” 由于您的循环从 0 到 N，至少，您正在做 O(N) 的工作。

    空间复杂度可以看作是“在这个算法中我使用了多少空间？” 您无需制作任何额外的数组，因此您的空间复杂度约为 O(N)。

  3. 你真的应该重新审视你的算法如何比较重复的数字。但我把它作为练习留给你。

*：您的代码也没有找到数组中的所有重复项。你可能想重新审视它。

于 2012-06-20T23:05:11.777 回答
0 
public boolean hasDuplicates(int[] arr) {
    boolean found = false;
    for (int i = 1 ; i <= arr.length ; i++) {
        for (int a : arr) 
            if (a == i) found = true;
        if (! found) return true;
    }
    return false;
}

我相信这种方法会奏效（因为你目前没有）。它是 O(n^2)。

我很确定不可能在时间和空间上都达到 O(n)，因为需要两个嵌套的 for 循环，从而增加了方法的复杂性。

编辑

我错了（有时承认这一点很好），这是 O(n)：

public boolean hasDuplicates(int[] arr) {
    int[] newarr = new int[arr.length];
    for (int a : arr) newarr[a - 1]++;
    for (int a : newarr) if (a != 1) return true;
    return false;
}
  1. 是的，输入数组没有被破坏。
  2. 上面的方法是 O(n) （我的意思是它的运行时间和空间需求将随着参数数组长度线性增长）。
  3. 是的，见上文。
于 2012-06-20T23:13:54.080 回答
0

可以通过将所有元素添加到哈希集 = O(n)，然后将哈希集中的值的数量与数组的大小进行比较 = O(1)。如果它们不相等，则存在重复项。

与创建一个整数数组来计算每个元素相比，创建哈希集平均占用的空间也更少。这也是从 2n 到 n 的改进，尽管这对 big-O 没有影响。

于 2012-06-21T22:37:31.617 回答
-1

1）这不需要太多的努力，并且保持阵列完好无损：

 public boolean isArrayContainsDuplicates(int [] intArray){
  int expectedOutPut = (intArray.length*(intArray.length+1))/2;
  int actualOutput = 0;
  for(int i =0 ; i < intArray.length; i++){
   if(intArray[i]>intArray.length)return true;
   actualOutput += intArray[i];
  }
  return expectedOutPut == actualOutput ? false: true;
 }

2）这将需要接触数组中不同数量的元素。最好的情况是，它命中第一个元素 O(1)，平均情况是它命中中间 O(log n)，更糟糕的情况是它一直通过并返回 false O(n)。

O(1) 指的是一些与项目总数无关的操作。在这种情况下，第一个元素将是唯一具有这种情况的元素。

O(log n) - log 是一个限制因素，可以是从 0 到 1 的实数。因此，乘以 log 将导致较小的数字。因此，O(log n) 是指所需的操作数量少于项目的数量。

O(n) - 这是当它需要的操作数等于项目数时。

这些都是所需时间的大符号。

该算法使用的内存将随着 n 的增加而增加。然而，它不会线性增长，而是大小 n 的一小部分，因此它的空间 Big-O 为 O(log n)。

3) 是的，这是可能的——但是，只有在最好的情况下才有可能。

于 2012-06-20T23:13:43.067 回答