我最近在解決一個問題。問題簡單地詢問以下問題，給定范圍為 1 到 n 的整數串列，找到串列中的第一個重復值，
現在顯而易見的解決方案是使用哈希表并在 O(n) 空間和 O(n) 時間內完成，但我發現有一個巧妙的技巧可以用來在 O(1) 空間中解決它。
我們可以只迭代陣列，然后 for a[i]，我們將索引標記a[a[i]]為負數，然后我們只需檢查之前是否已將任何整數設為負數，如果是，那就是第一個重復值。
我的問題是，如果陣列中也有負值怎么辦？有沒有通用的方法來解決這個問題？
uj5u.com熱心網友回復：
如果陣列中也有負值怎么辦？
如果您的意思是值在 -?? 1...?? 或 -??...??-1,... 的范圍內，使得可能值的計數為 2??，那么您可以保留 2 位而不是 1 位用于在陣列中放置標志：一個用于當值為正時，一個用于當它為負時，或者您想將值范圍分成兩個的任何方式。
在您的解決方案，你已經使用了符號位，這32位整數通常最左邊的位，或32次位，所以你可以決定保留31日位作為第二個標志。這意味著 ?? 不應大于 2 30 -1。
uj5u.com熱心網友回復：
存盤陣列本身的空間復雜度為 O(n)。如果您關心使用的額外空間，您所做的就是使用負值作為 1 位存盤的標志，這將您可以存盤的值范圍減少 1 位。您可以提出任意數量的方案來在某處存盤額外的標志位：例如，處理 int_min/2 和 int_max/2 之間的值，您可以將所有值向上移動為非負，然后使用符號位，但是除非您的記憶體受到嚴重限制，否則在實際應用中是不值得的。對于真正的大資料操作，您甚至無法存盤整個陣列，您可以使用諸如 count-min 草圖之類的概率在線方法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313567.html