問題說要刪除重復的數字。然后，將數字保留在一個數組中，不要重復其他數字。例如， [0, 0, 1, 1, 2, 2, 1, 1 , 2, 2] 將是 [0, 1, 2 ] 這些數字應為時間復雜度 Big O(n) 和空間復雜度 O (1).到目前為止，我所擁有的是下一個數字，檢查下一個數字。它沒有得到比它更遠的數字。例如： [ 0, 1, 2 ,3 , 4, 5, 6, 2, 8, 9 ] 2 距離較遠，但下面的代碼不會檢查。D[i+1]我無法使用哈希圖或哈希集。 while (i < A.length) { i++; D = A; if (i < A.length - 1) { if (A[i] == D[i+1]){ B[i] = D[i + 1]; } else A[i] = A[i]; } }
3 回答
森林海
TA貢獻2011條經驗 獲得超2個贊
如果輸入數組未排序（并且根據您的說法 - 未排序），您將無法在O(n)時間和空間上完成任務。O(1)
這是不可能的，因為為了刪除元素，您必須檢查數組中之前或之后的任何位置是否有重復項。
要檢查重復項，您必須：
掃描輸入數組（這將導致
O(n^2)整個算法的時間）使用額外的空間，例如使用
Set（這將導致O(n)時間和O(n)空間）。
所以基本上你必須權衡時間和空間，反之亦然。
明月笑刀無情
TA貢獻1828條經驗 獲得超4個贊
這可能是不可能的，除非數組使用鏈表進行排序或將元素標記為 Integer.MIN_VALUE，應用此原則的“空間和時間權衡”如果我們需要更快的時間，那么我們需要權衡空間，反之亦然。
如果使用數組，那么您可以將重復元素標記為 Integer.MIN_VALUE（在 java 中或在 c/c++ 中 -2^16），并且可以忽略該值。
如果使用鏈表并且數組已排序，則只需檢查下一個節點與前一個節點并刪除下一個重復節點。
慕容708150
TA貢獻1831條經驗 獲得超4個贊
您必須“檢查所有前面的內容”，而不是“檢查下一個”。
那么問題就變成了，“如何檢查一個數字在恒定時間內是否存在于任意數量的其他元素中”？
使用一個HashSet. 基于哈希的結構的所有操作都是 O(1)。
add()考慮使用和contains()的兩種方法HashSet。
我把寫的代碼留給你......
添加回答
舉報
0/150
提交
取消