寫一個函數來從數組中刪除重復的對象。維持秩序。例如，如果輸入的數組[ 1，5，4，2，7，2，6，5 ]，結果應該是[ 1，5，4，2，7，6 ]。實施時應執行速度的優化。
2 回答
瀟湘沐
TA貢獻1816條經驗 獲得超6個贊
最快的算法肯定是O(n)
具體做法是：
1，準備一個HashMap或者HashTable
2，循環你的輸入數組，判斷他是否在HashMap中，如果不是，輸出，并且加入到HashMap中（比如：Map.put(1,true)），如果是在HashMap中則什么都不做。
因為HashMap的讀取和設置是O(1)的時間復雜度，所以加上循環整體的時間復雜度也是O(n)
寶慕林4294392
TA貢獻2021條經驗 獲得超8個贊
難點
1)數組,如果是鏈表可能會比較容易些:也就是移走重復的后,不能留下空洞
2)去重:應該是只需要掃描數組一遍,否則性能不太好.
3)排序的穩定,也就是順序保持不變.
方案:
使用Bitmap來依次檢查重復
如果重復, 則后面所有的數組節點往前移一個位置. 具體的代碼可以參考ArrayList.remove()
如果沒有重復,遍歷數組下一節點
評價:
只需要引入一個Bitmap,內存消耗非常小
檢索去重,性能很快,只需要一次運算即可
不需要使用一個新的數組來對考
添加回答
舉報
0/150
提交
取消