[LeetCode]#1122. Relative Sort Array

Environment: Python 3.7

Key technique: {},setdefault

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

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]

Analysis:

1. Use dict function for arr2 to record element. (d1)
2. Use dict function for arr1 to check whether match arr2 or not. Record the number. (d2)
3. Check mismatch element.
4. Sort d2 based on d1 order and add mismatch.

Solution:

class Solution:
    def relativeSortArray(self, arr1, arr2):
        d1 = {}
        for i in arr2:
            d1[i] = 1
not_match = []
        d2 = {}
        for i in arr1:
            if i in d1:
                d2[i] = d2.setdefault(i,0) + 1
            else:
                not_match.append(i)
        match = []
        for i in arr2:
            match += [i] * d2[i]
        return match + sorted(not_match)

Submission:

Reference:

【leetcode】1122. Relative Sort Array

https://www.runoob.com/python/att-dictionary-setdefault.html