Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

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: 大師
→ DJYOSHITAKA: 別捲了 不行了
推 argorok: 大師
→ sustainer123: ez 別這樣
→ sustainer123: 今天ez
推 JIWP: 對你來說什麼都是ez
推 oin1104: 大師
推 digua: 大師
→ wu10200512: 卷不動了 放過我
→ Rushia: 第二個方法一定比較快阿
→ sustainer123: submit差不多 數量太少吧