0

私は一連のようなものを持っており1,2,199,100,8,100,199,1001,5,9、上記のリストに複数回現れる数字を見つけるために疑似コードを書かなければなりませんでした。199 と 100 がリストに 2 回表示されていることがはっきりとわかります。これが答えになるはずですが、その疑似コードをどのように記述すればよいでしょうか? 私のロジックは次のようなものです：

   array x = {1,2,199,100,8,100,199,1001,5,9}
   array y
   array j
for(int i = 0;i< 9; i++){
 if x[i] exists in y
     j[i] = y
 else
    y[i] = x


}
4

4 に答える 4

1

exists() チェックを使用すると、バブル ソートと同じパフォーマンスが得られるように見えます。配列をソートして（より高速なソートで）、重複を識別するために1回余分にパスを実行すると、おそらくより高速になります。あなたの疑似コードを正しく理解していれば、バグがあるようです。それはもっと似ているべきではありません：

for(int i = 0;i< 9; i++){
 if x[i] exists in y
     j.push(x[i]);
 else
    y.push(x[i]);    

}
于 2012-01-18T18:02:49.617 に答える
1

クイック ソートまたはマージ ソート (n log n) でリストをソートし、現在の数値を以前の O(n) と比較して、リストを 1 回パスします。前の数が現在の数と等しい場合は、重複があります。

編集：

Array array = {1,2,199,100,8,100,199,1001,5,9}
Array sorted = sort(array)
for (int i=1; i<sorted.length; i++)
    int p = sorted[i-1]
    int c = sorted[i]
    if (p==c) print "duplicate"
于 2012-01-18T18:12:42.973 に答える
0

を使用できるのではなく、プリミティブ型のみを使用するように制限されていると仮定するとjava.util.Collections、次のように作業できます。

For each value in `x`
  Grab that value
  If the list of duplicates does not contain that value
    See if that value reoccurs at a later index in `x`
      If it does, add it to the list of duplicates

Java に変換された疑似コードは次のとおりです。

private void example() {
    int [] x = new int [] {1,2,199,100,8,100,199,1001,5,9, 199};
    int [] duplicates = new int[x.length];

    for (int i = 0; i < x.length; i++) {
      int key = x[i];
      if (!contains(duplicates, key)) {
        // then check if this number is a duplicate
        for (int j = i+1; j < x.length-1; j++) {
          // start at index i+1 (no sense checking same index as i, or before i, since those are alreayd checked
          // and stop at x.length-1 since we don't want an array out of bounds exception
          if (x[j] == key) {
            // then we have a duplicate, add to the list of duplicates
            duplicates[i] = key;
          }
        }
      }
    }

    for (int n = 0; n < duplicates.length; n++) {
      if (duplicates[n] != 0) {
        System.out.println(duplicates[n]);
      }
    }
}

  private boolean contains(int [] array, int key) {
    for (int i = 0; i < array.length; i++) {
      if (array[i] == key) {
        return true;
      }
    }
    return false;
  }
于 2012-01-18T18:29:12.230 に答える
0 
// loop through list of numbers
    // count apperences in list
    // if appearences > 1
            // remove all instances, add to results list

// print the results list -- this will have all numbers that appear more than once.
于 2012-01-18T17:50:18.330 に答える