排序的java数组中的重复项

Question

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

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 -重复)
• 对数组执行另一次运行，在新数组中放置唯一值。

由于数组是排序的，您可以只检查arrayn == arrayn+1，如果不是，那么它不是复制的。在检查n+1时，要小心数组边界。

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

Answer 2

测试和工作(假设数组已经被排序)

public static int[] noDups(int[] myArray) { 

    int dups = 0; // represents number of duplicate numbers

    for (int i = 1; i < myArray.length; i++) 
    {
        // if number in array after current number in array is the same
        if (myArray[i] == myArray[i - 1])
            dups++; // add one to number of duplicates
    }

    // create return array (with no duplicates) 
    // and subtract the number of duplicates from the original size (no NPEs)
    int[] returnArray = new int[myArray.length - dups];

    returnArray[0] = myArray[0]; // set the first positions equal to each other
                                 // because it's not iterated over in the loop

    int count = 1; // element count for the return array

    for (int i = 1; i < myArray.length; i++)
    {
        // if current number in original array is not the same as the one before
        if (myArray[i] != myArray[i-1]) 
        {
           returnArray[count] = myArray[i]; // add the number to the return array
           count++; // continue to next element in the return array
        }
    }

    return returnArray; // return the ordered, unique array
}

我的先前的回答用Integer List来解决这个问题。

Answer 3

不创建一个新数组肯定会导致整个初始数组的空值。因此，创建一个新的数组来存储来自初始数组的唯一值。

如何检查唯一的值？这是伪代码

uniq = null
loop(1..arraysize)      
  if (array[current] == uniq)  skip
  else  store array[current] in next free index of new array; uniq = array[current]
end loop

另外，正如其他人提到的，通过对数组的初始扫描获得数组大小。

uniq = null
count = 0
loop(1..arraysize)      
  if (array[current] == uniq)  skip
  else  uniq = array[current] and count++
end loop
create new array of size count