問題描述

我必須編寫一個方法，該方法接受一個已經按數字順序排序的整數數組，然后刪除所有重復的數字并返回一個僅包含沒有重復的數字的數組.然后必須打印出該數組，因此我不能有任何空指針異常.該方法必須在 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.

這篇關于已排序的 java 數組中的重復項的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！