※ 引述《JIWP (神楽めあ的錢包)》之銘言： : 2179. Count Good Triplets in an Array : 題目的意思就是要找這樣的排列[a,b,c]有幾種 : 其中a,b,c,的先後順序在nums1、nums2都一樣 : 思路: nums1 和 nums2 都是 (0~n-1) 的 premutation 先思考怎麼找到 good pair 好了 可以想像要先做一個 idx 轉換 nums1[i] 的這個數字在 nums2 的 index 是多少 然後就可以從左開始 iterate nums1 把他們在 nums2 的 index 做成 sortedlist 直接二分搜這個 sortedlist 就可以知道有多少數字在 nums2 也同樣靠前 以 nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3] 為例好了 iterate nums1: 4 -> idx in s2 = 0, sorted index = [0] 0 -> idx in s2 = 2, sorted index = [0,2] 1 -> idx in s2 = 1, sorted index = [0,1,2] 3 -> idx in s2 = 4, sorted index = [0,1,2,4] 2 -> idx in s2 = 3, sorted index = [0,1,2,3,4] 挑 (1,4) 這個合法 pair 來觀察好了 在 iterate 到 1 的時候 還沒插入的 sorted index 是 [0,2] 他們代表 4,0 在 s2 中的 index 是多少 而 1 在 s2 的 index 是 1, 二分搜就可以知道有多少 index 在 s2 中也同樣比較小 要怎麼擴展到 triplet 就可以想像假如 iterate 到 s1[3]=516, s1[3] 在 s2 的 index 是 4 那 s1 s2 應該會長這樣 s1 = [x, x, x, 516, ......] s2 = [y, y, y, y, 516, ......] 我們剛剛知道可以用 sortedlist 知道 x 中有幾個也在 y 裡面, 如果是 2 個好了 s1 = [0, 1, x, 516, ......] s2 = [y, y, 0, 1, 516, ......] 合法的 triplet 就可以用 {(0,1), 516, 剩下的數字-x-y} 算出來 同時 xy 沒有相同元素 寫成 prev * 1 * pos 的話 prev = len([0,1]) 代表的就是剛剛 sorted index 二分搜出來的值 pos = len(剩下的數字-x-y) 直接看 s2 會比較清楚 因為 s2 長相差不多是 [y, y, 0, 1, 516, ......, x, ......] 所以就是用 len(n) - (516 在 s2 的 index + 1) - (x 的個數) x 的個數就是 iterate s1 的 index - prev 不想寫了 我自己快看不懂了 Python code: class Solution: def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int: n = len(nums1) idx2 = [0]*n res = 0 for i in range(n): idx2[nums2[i]] = i prevIdx = SortedList([]) for i in range(n): idx1in2 = idx2[nums1[i]] prev = prevIdx.bisect_left(idx1in2) prevIdx.add(idx1in2) pos = n - (idx1in2 + 1) - (i - prev) res += prev*pos return res 喔對了 因為 python sortedlist 插入是 O(logn) 才能這樣 不然只能乖乖用線段樹或BIT 哈哈 -- 沒人在乎 -- ※ 發信站: 批踢踢實業坊(ptt-club.com.tw), 來自: 1.162.75.117 (臺灣) ※ 文章網址: https://ptt-club.com.tw/Marginalman/M.1744736689.A.ADF

推 Rushia: 唉 恨屁眼 04/16 01:05

→ oin1104: 幹 我他媽哭了 我今天這題寫超久沒寫出來直接抄線段書 04/16 01:07

→ oin1104: 我好痛苦 04/16 01:07

→ oin1104: 我好崇拜你 04/16 01:07

→ pandix: 如果是周賽我也直接複製模板ㄚ 對ㄚ 04/16 01:08

推 wilmer: 有人被洋鬼子包養過嗎 04/16 01:08

推 JIWP: 我原本也是用二分搜尋，不過插入會爆掉，恨恨恨 04/16 01:08

→ pandix: 這就是SortedList的不合理之處 04/16 01:10

推 JIWP: 害我跑去刻那該死的線段樹 04/16 01:11