Re: [閒聊] 每日leetcode已回收

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/06/11 10:39)推噓5(5推 0噓 6→)

留言11則, 8人參與討論串339/1548 (看更多)

https://leetcode.com/problems/relative-sort-array 1122. Relative Sort Array 給定兩數列arr1與arr2 arr2的元素不重復且皆存在於arr1 請依照arr2的順序排列arr1的元素假設有元素不在arr2 請遞增排序 Example 1: Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] Output: [2,2,2,1,4,3,3,9,6,7,19] Example 2: Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] Output: [22,28,8,6,17,44] Constraints: 1 <= arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 All the elements of arr2 are distinct. Each arr2[i] is in arr1. 思路: 記數排序但不在arr2的元素要多付出一個sort排序所以時間複雜度是nlogn Python Code: class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: record = defaultdict(int) exception = [] for n in arr1: if n in arr2: record[n] += 1 else: exception.append(n) i = 0 for n in arr2: c = record[n] while c > 0: arr1[i] = n c -= 1 i += 1 exception.sort() while exception: x = exception.pop(0) arr1[i] = x i += 1 return arr1 思路二: 改用list紀錄因為元素最大就1000 所以開一個1001大小的list 最後從0開始由小到大遍歷list 遇到不在arr2的元素就加進去arr1 這樣就可以省下一個sort 時間複雜度是n Python Code: class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: record = [0] * 1001 for n in arr1: record[n] += 1 i = 0 for n in arr2: while record[n] > 0: arr1[i] = n record[n] -= 1 i += 1 for j in range(1001): while record[j] > 0: arr1[i] = j record[j] -= 1 i += 1 return arr1 不過第二種方法也沒比較快就是了而且不用對原列表修改其實直接做一個新列表比較快姆咪 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.220.48 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718073545.A.3EA.html

推

JIWP

06/11 10:40, 1年前 , 1^F

06/11 10:40, 1^F

→

DJYOSHITAKA

06/11 10:40, 1年前 , 2^F

06/11 10:40, 2^F

推

argorok

06/11 10:40, 1年前 , 3^F

06/11 10:40, 3^F