我有一組 32 位整數，我將用它制作一個資料結構，將這些整數放在不同的組件中（如 dsu），連接操作必須使用按位和執行，如果按位和不是兩個整數的零它們位于同一個組件中，現在給定一個整數，我如何獲得（假設已經為此當前整數的前綴創建了資料結構）該整數所在的組件？例如，給定 [1,5,3,8] 的一組整數比 (1,5,8) 位于一個組件中，因為任何對的 lsb 都將確保非零“位和”，并且 (8) 將位于它自己的組件中組件，或者很可能完全不同的演算法，如果你能想到更簡單的演算法，
編輯 ：
然而，有可能兩個整數具有位和為零，但如果引入第三個整數，它具有成對位且兩者都非零，那么所有三個整數都將位于相同的分量 ex [2,12, 6] 2 和 12 中給 0 但 2 和 6 不給， 12 和 6 不給，所以 6 將所有三個統一為一個組件。
編輯 2：我能夠想到一種使用 32 長度陣列的簡單演算法，其中一個條目由類似結構的鏈表（如鄰接表）組成，如果設定了第 i 位，則索引 i 將包含所有整數我設定了位，但它可以給我 O(n) 搜索，我更多地考慮 dsu，但發現很難創建它。
uj5u.com熱心網友回復：
這是一些將組件表示為不相交位掩碼串列的go 代碼（可運行鏈接） 。先前看到的整數在它具有非零按位與的分量中（或零分量，如果它為零）。
可以通過查找具有非零位與的所有組件并將它們替換為作為這些組件和新元素的位或的單個組件來使用新整數更新組件串列。
在任何輸入值中，每位最多有一個分量，如果有零分量，則加一個分量。這里最多有 32 個分量，因為輸入值被宣告為 32 位。
package main
import (
"fmt"
)
// makeComponents returns a slice of disjoint bitmasks
// that represent the different components in the input.
func makeComponents(xs []uint32) []uint32 {
var cs []uint32
for _, x := range xs {
j := 0
for i, c := range cs {
cs[j] = cs[i]
if c & x != 0 || (x == 0 && c == 0) {
x |= c
} else {
j
}
}
cs = append(cs[:j], x)
}
return cs
}
// component returns the component (from cs) that x is in.
func component(cs []uint32, x uint32) int {
for i, c := range cs {
if x==c || x & c != 0 {
return i
}
}
panic("no component")
}
// showComponents outputs the input values with those in the same
// component on the same line.
func showComponents(xs []uint32) {
cs := makeComponents(xs)
xperc := make([][]uint32, len(cs))
for _, x := range xs {
c := component(cs, x)
xperc[c] = append(xperc[c], x)
}
for _, xc := range xperc {
fmt.Println(xc)
}
}
func main() {
xs := []uint32{0, 1, 3, 6, 8, 16, 48, 65}
showComponents(xs)
}
uj5u.com熱心網友回復：
這些要求意味著當且僅當與（中所有數字的按位或）的按位與非零時，x應將傳入整數與組件連接。CxC
一個不相交的資料結構可以很好地解決這個問題。每個組件的“根”還可以維護其所有成員的按位或，這可以使用單獨的哈希圖完成，盡管這不是絕對必要的。
您還應該保留從每個位位置到具有該位位置集的（唯一，如果存在）組件的任何成員的哈希圖。添加新整數時，掃描其所有設定位：使用此哈希圖查找要合并的所有組件，或者是否創建新組件。這應該提供幾乎恒定的時間更新。任何時候最多也有1 ceil(log_2(M))不同的分量，M你見過的最大整數是哪里，最多是 33。
如果您想避免不相交集代碼的某些復雜性，您可以使用Paul Hankin 的組件串列建議。根據您的編程語言以及是否要計算重復項，組件可以表示為（位掩碼，多重集）對，其中位掩碼是所有成員的按位或，并且成員的多重集允許您列印一個的所有成員組件并及時測驗遏制O(1)，盡管插入可能需要更長的時間（但仍然是恒定的攤銷時間）。
如果您從不需要列印組件的成員或檢查是否實際添加了特定整數，只需存盤位掩碼就足夠了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424336.html
上一篇：獲取凸包索引