已排序的 java 数组中的重复项

2022-01-10 00:00:00 arrays sorting duplicates java

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

I have to write a method that takes an array of ints that is already sorted in numerical order then remove all the duplicate numbers and return an array of just the numbers that have no duplicates. That array must then be printed out so I can't have any null pointer exceptions. The method has to be in O(n) time, can't use vectors or hashes. This is what I have so far but it only has the first couple numbers in order without duplicates and then just puts the duplicates in the back of the array. I can't create a temporary array because it gives me null pointer exceptions.

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;
}

推荐答案

由于这似乎是作业，我不想给你确切的代码，但这里是做什么:

Since this seems to be homework I don't want to give you the exact code, but here's what to do:

  • 对数组进行第一次遍历，看看有多少重复项
  • 创建一个新的大小数组(oldSize - 重复)
  • 再次遍历数组以将唯一值放入新数组中

由于数组已排序，您只需检查 array[n] == array[n+1].如果不是，那么它不是重复的.检查 n+1 时请注意数组边界.

Since the array is sorted, you can just check if array[n] == array[n+1]. If not, then it isn't a duplicate. Be careful about your array bounds when checking n+1.

因为这涉及到两次运行，它将在 O(2n) -> O(n) 时间内运行.

edit: because this involves two run throughs it will run in O(2n) -> O(n) time.

相关文章