在排序的java數組中重複

Question

我必須編寫一個方法，它接受一個已經按數字順序排序的int數組，然後刪除所有重複數字並返回一個沒有重複數字的數組。該數組必須被打印出來，所以我不能有任何空指針異常。該方法必須在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 - 重複）
• 做一套貫穿於陣列把唯一值的新陣列中的

由於數組已排序，因此可以檢查array [n] == array [n + 1]。如果不是，那麼它不是重複的。檢查n + 1時，請注意您的數組邊界。

編輯：因爲這涉及兩個運行，它將運行在O（2n） - > O（n）時間。

Answer 2

不創建新的數組肯定會導致整個初始數組中的空值。因此，創建一個新的數組來存儲初始數組中的唯一值。

如何檢查唯一值？下面是僞代碼

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 3

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 4

測試和工程（假設數組已經訂購）

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 
} 

我的previous answer這個問題用了IntegerList。

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<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)。