java - 在排序的java数组中重复

Question

我必须编写一个方法，该方法采用已按数字顺序排序的整数数组，然后删除所有重复数字并返回一个仅包含没有重复数字的数组。然后必须打印出该数组，这样我就不会出现任何空指针异常。该方法必须在 O(n) 时间内，不能使用 vector 或哈希。这是我到目前为止所拥有的，但它只有前几个数字没有重复，然后只是将重复项放在数组的后面。我无法创建临时数组，因为它会给我空指针异常。

public static int[] noDups(int[] myArray) {
    int j = 0;
    for (int i = 1; i < myArray.length; i++) {
        if (myArray[i] != myArray[j]) {
            j++;
            myArray[j] = myArray[i];
        }
    }
    return myArray;
}

Answer 1

因为这似乎是家庭作业，所以我不想给你确切的代码，但这是要做的:

• 首先遍历数组以查看有多少重复项
• 创建一个新的大小数组(oldSize - 重复项)
• 再遍历数组以将唯一值放入新数组

由于数组已经排序，你可以只检查是否array[n] == array[n+1]。如果不是，那么它不是重复的。检查 n+1 时请注意数组边界。

编辑:因为这涉及两次遍历，它将在 O(2n) -> O(n) 时间内运行。