快速算法簡單的數據組

有幾十億行這樣快速算法簡單的數據組

id | type | groupId 
---+------+-------- 
1 | a | 
1 | b | 
2 | a | 
2 | c | 
1 | a | 
2 | d | 
2 | a | 
1 | e | 
5 | a | 
1 | f | 
4 | a | 
1 | b | 
4 | a | 
1 | t | 
8 | a | 
3 | c | 
6 | a |

我需要，添加的groupId對於這些數據，如果ID相同或鍵入相同的，那麼其在相同的groupId，結果是這樣的：

id | type | group 
---+------+-------- 
1 | a | 1 
1 | b | 1 
2 | a | 1 
2 | c | 1 
1 | a | 1 
2 | d | 1 
2 | a | 1 
1 | e | 1 
5 | a | 1 
1 | f | 1 
4 | a | 1 
1 | b | 1 
4 | a | 1 
7 | t | 2 
8 | g | 3 
3 | c | 1 
6 | a | 1

我嘗試使用循環來做到這一點，但它效率非常低，需要服務器幾周來完成所有這些。

來源

2016-05-27 user1203286

顯示你的算法。 –

-1

這是一個典型的例子，您可以使用一個Quick-Union算法。

計算限制

進行分組N行

時間複雜度：O（N日誌* N），其中log * N是「，採取了許多的LG直到需要次數達到1「。例如登錄* 10^100 = 3（約）
空間複雜：O（N）

瞭解更多關於這種算法：

來源

2016-05-27 02:58:35

正確，但缺少關鍵幫助：要針對此問題使用聯合查找算法，請爲每個唯一ID初始設置一個初始值，併爲每個唯一類型設置一個初始值。合併出現在同一行中的任意兩個集合。爲每個最終集分配一個groupid。該行的groupid然後是包含其id和類型集的最終集合的groupid。注意：我沒有downvote這個答案 –

關於爲每個唯一的ID初始設置，我覺得這是一個非常基本的應用算法和觀看我鏈接的視頻的人會做的基本事情。關於爲每個最終集合分配一個groupid，這將通過算法完成，並且您將在算法結束時爲每個組獲得唯一的id。 –

快速算法簡單的數據組

回答

相關問題