PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 多個set作交集

看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (閉上眼的魚)時間12年前 (2012/10/02 23:23)推噓2(2推 0噓 5→)

留言7則, 3人參與討論串2/3 (看更多)

※ 引述《chunhsiang (= =)》之銘言： : 假設集合A與B作交集 n=|A| m=|B| : 只需要O(n+m)

推

EdisonX

10/02 22:54,

10/02 22:54

→

chunhsiang

10/02 22:59,

10/02 22:59

推

EdisonX

10/02 23:00,

10/02 23:00

回文說明較清楚。虛碼部份以 C 大致示之。假設 A = {200,-1,2,100}, B={-100,-1,200,2}, 不一定要照順序 (1) 先掃 A, B 一遍，紀錄整體最大、最小值，Max, Min (200, -100) (2) 如果每個數字都用一個位元表示的話，需要 Max - Min + 1 = 301 bits 假設一個無號數 (unsigned int ) 佔了 32 bits ，可計算出，需要陣列的大小約是 301 / 32 + 1 = 10 <不考慮剛好是32整數bit問題> unsigned ASet[10]={0U}, BSet[10]={0U}; unsigned idx; /*這用來計算到時候放在陣列哪個 idx*/ unsigned bit; /*這用來計算到時候放在陣列哪個 bit*/ (3) 先 polling A, B (3.1) 紀錄 200 : 200-Min=300, idx=300/32 = 9, bit = 300%32=12 ASet[idx] |= (1U<<bit); (3.2) 紀錄 -1 : -1-Min=99, idx=99/32 = 3, bit =99%32=3 ASet[idx] |= (1U<<bit); .... (4) 計算結果 unsigned Rst[10]; for(i=0; i<10; ++i) Rst[i] = ASet[i] & BSet[i]; 最後要輸出的時候再根據 Rst 內容做輸出。 (1) : O(n+m) (2) : O(1) (3) : O(n+m) (4) : O(n+m) 整體應該還算 O(n+m) <吧？> 但如上所見，有幾個缺點 (1) 只適用整數集合 (2) Max-Min 過大的時候就浪費記憶體 <情況不要太偏激的話，記憶體應都還堪用> 非整數、稀疏、範圍大時，可能就不適用。不知您的情況是？？ -- 「自從我學了 C# , 人都變聰明 , 考試都考一百分」「自從我學了 VB , 皮膚都變好 , 人也變漂亮了」「自從我學了 Java , 明顯變壯 , 個子也變高了」「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.161 ※ 編輯: EdisonX 來自: 180.177.76.161 (10/02 23:28)