1

私は課題に取り組んでいますが、いくつかの質問に対する回答が得られません。

私は尋ねられました：

入力: 1 から N までの整数のみを含む長さ N の配列 A

出力: 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 は任意の数になる可能性があるため、これは No にする必要があります。繰り返しますが、O(n) についてはよくわかりません。

ありがとう

4

5 に答える 5

2

入力配列 A を破壊せずに答えを提供することは可能ですか?

はい。たとえば、かかる時間を気にしない場合は、可能な数ごとに配列を 1 回ループして、正確に 1 回表示されるかどうかを確認できます (そうでない場合は、重複があるはずです)。それはO（N ^ 2）になります。

ただし、通常は、追加の配列 (または他のデータ構造) をスクラッチ リストとして使用します (これも入力配列を破棄しません。以下の 3 番目の質問を参照してください)。

アルゴリズムの時間と空間の複雑さを分析しますか?

アルゴリズムは O(n) で実行され、入力配列に対して 1 回のパスのみを実行し、追加のスペースは必要ありません。しかし、うまくいきません。

時間と空間の両方で O(n) は可能ですか?

はい。

同じサイズ (サイズ = N) の別の配列を用意し、すべての数値が表示される頻度をカウントし (入力を 1 回通過)、カウントを確認します (出力を 1 回通過するか、エラーが発生した場合は短絡します)。

したがって、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

すべての要素をハッシュセット = O(n) に追加し、ハッシュセット内の値の数を配列のサイズ = O(1) と比較することで可能です。それらが等しくない場合、重複があります。

また、ハッシュセットを作成すると、整数配列を作成して各要素をカウントするよりも、平均して占有するスペースが少なくなります。また、2n から n への改善ですが、big-O には影響しません。

于 2012-06-21T22:37:31.617 に答える
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)です。

ネストされた 2 つの for ループが必要になり、メソッドの複雑さが増すため、時間と空間の両方で O(n) を達成することは不可能であると確信しています。

編集

私は間違っていました (時にはそれを認めるのが良いこともあります)、これは 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 に答える
-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 に答える