伪代码查找列表中多次出现的数字

Question

我有一个像 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


}

Answer 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"

Answer 2

通过exists() 检查，这看起来与冒泡排序具有相同的性能。如果您对数组进行排序（使用更快的排序），然后再执行一次额外的操作来识别重复项，那么可能会更快。
如果我正确理解你的伪代码，它似乎有一个错误。难道不应该更像是：

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

}

Answer 3

// 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.

Answer 4

假设您仅限于使用基本类型而不能使用 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;
  }