1

我必须编写一个方法，该方法接受一个已经按数字顺序排序的整数数组，然后删除所有重复的数字并返回一个仅包含没有重复的数字的数组。然后必须打印出该数组，因此我不能有任何空指针异常。该方法必须在 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;
}
4

5 回答 5

4

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

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

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

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

于 2013-10-18T04:07:48.130 回答
1

经过测试并且可以工作（假设数组已经订购） 

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.

于 2013-10-18T04:22:24.773 回答
0 
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;
}
于 2013-10-18T04:19:49.393 回答
0

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

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

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
于 2013-10-18T04:15:16.353 回答
0 
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<arr.length-2; i++){
        if(arr[i] != arr[i+1]){
            res[j] = arr[i];
            j++;
        }
    }
    // copy the last element
    res[j]=arr[arr.length-1];
    j++;
    // now move the result into a compact array (exact size)
    int[] ans = new int[j];
    for(int i=0; i<j; i++){
        ans[i] = res[i];
    }
    return ans;
}

第一个循环是O(n)，第二个循环也是如此 - 根据要求总计O(n)。

于 2013-10-18T06:11:54.900 回答