Re: [閒聊] 每日leetcode

看板Marginalman作者pandix (麵包屌)時間7月前 (2025/04/16 01:04)推噓3(3推 0噓 5→)

※ 引述《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.cc), 來自: 1.162.75.117 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1744736689.A.ADF.html

推

Rushia

04/16 01:05, 7月前 , 1^F

04/16 01:05, 1^F

→

oin1104

04/16 01:07, 7月前 , 2^F

04/16 01:07, 2^F

→

oin1104

04/16 01:07, 7月前 , 3^F

04/16 01:07, 3^F