在已排序的Java数组中重复

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

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）时间运行。

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 

Answer 4

 public static int[] findDups(int[] myArray) { int numOfDups = 0; for (int i = 0; i < myArray.length-1; i++) { if (myArray[i] == myArray[i+1]) { numOfDups++; } } int[] noDupArray = new int[myArray.length-numOfDups]; int last = 0; int x = 0; for (int i = 0; i < myArray.length; i++) { if(last!=myArray[i]) { last = myArray[i]; noDupArray[x++] = last; } } return noDupArray; } 

Answer 5

 public int[] noDups(int[] arr){ int j = 0; // copy the items without the dups to res int[] res = new int[arr.length]; for(int i=0; i 

第一个循环是O(n) ，第二个循环也是如此 - 它按照要求总计为O(n) 。