首頁(yè) 猿問(wèn) 刪除到目前為止的重復(fù)數(shù)字刪除下一個(gè)...

刪除到目前為止的重復(fù)數(shù)字刪除下一個(gè)數(shù)字 Big O(n)

Java

動(dòng)漫人物 2023-07-28 10:22:21

問(wèn)題說(shuō)要?jiǎng)h除重復(fù)的數(shù)字。然后，將數(shù)字保留在一個(gè)數(shù)組中，不要重復(fù)其他數(shù)字。例如， [0, 0, 1, 1, 2, 2, 1, 1 , 2, 2] 將是 [0, 1, 2 ] 這些數(shù)字應(yīng)為時(shí)間復(fù)雜度 Big O(n) 和空間復(fù)雜度 O (1).到目前為止，我所擁有的是下一個(gè)數(shù)字，檢查下一個(gè)數(shù)字。它沒(méi)有得到比它更遠(yuǎn)的數(shù)字。例如： [ 0, 1, 2 ,3 , 4, 5, 6, 2, 8, 9 ] 2 距離較遠(yuǎn)，但下面的代碼不會(huì)檢查。D[i+1]我無(wú)法使用哈希圖或哈希集。 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貢獻(xiàn)2011條經(jīng)驗(yàn) 獲得超2個(gè)贊

如果輸入數(shù)組未排序（并且根據(jù)您的說(shuō)法 - 未排序），您將無(wú)法在O(n)時(shí)間和空間上完成任務(wù)。O(1)

這是不可能的，因?yàn)闉榱藙h除元素，您必須檢查數(shù)組中之前或之后的任何位置是否有重復(fù)項(xiàng)。

要檢查重復(fù)項(xiàng)，您必須：

掃描輸入數(shù)組（這將導(dǎo)致O(n^2)整個(gè)算法的時(shí)間）
使用額外的空間，例如使用Set（這將導(dǎo)致O(n)時(shí)間和O(n)空間）。

所以基本上你必須權(quán)衡時(shí)間和空間，反之亦然。

反對(duì) 回復(fù) 2023-07-28

明月笑刀無(wú)情

TA貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超4個(gè)贊

這可能是不可能的，除非數(shù)組使用鏈表進(jìn)行排序或?qū)⒃貥?biāo)記為 Integer.MIN_VALUE，應(yīng)用此原則的“空間和時(shí)間權(quán)衡”如果我們需要更快的時(shí)間，那么我們需要權(quán)衡空間，反之亦然。

如果使用數(shù)組，那么您可以將重復(fù)元素標(biāo)記為 Integer.MIN_VALUE（在 java 中或在 c/c++ 中 -2^16），并且可以忽略該值。
如果使用鏈表并且數(shù)組已排序，則只需檢查下一個(gè)節(jié)點(diǎn)與前一個(gè)節(jié)點(diǎn)并刪除下一個(gè)重復(fù)節(jié)點(diǎn)。

反對(duì) 回復(fù) 2023-07-28