0

我有一个类似的系列1,2,199,100,8,100,199,1001,5,9，我必须编写一个伪代码来找出在上面的列表中出现多次的数字。我可以清楚地看到 199 和 100 在列表中出现了两次，这应该是答案，但我应该如何为其编写伪代码？我的逻辑是这样的：

   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() 检查，这看起来与冒泡排序具有相同的性能。如果您对数组进行排序（使用更快的排序）然后再进行一次额外的传递来识别欺骗，它可能会更快。如果我正确理解您的伪代码，它似乎有一个错误。不应该更像：

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) 进行比较。如果前一个数字等于当前数字，那么您有一个副本。

编辑：

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 
// 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 回答
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 回答