Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

preface

This is the second question in Biweekly Contest 73. It looks at sorting lists. On Medium, it uses Python’s built-in function sorted to solve the problem.

describe

You are given a 0-indexed integer array mapping which represents the mapping rule of a shuffled decimal system. mapping[i] = j means digit i should be mapped to digit j in this system.The mapped value of an integer is the new integer obtained by replacing each occurrence of digit i in the integer with mapping[i] for all 0 <= i <= 9.You are also given another integer array nums. Return the array nums sorted in non-decreasing order based on the mapped values of its elements.

Notes:

  • Elements with the same mapped values should appear in the same relative order as in the input.
  • The elements of nums should only be sorted based on their mapped values and not be replaced by them.

Example 1:

Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
Output: [338,38,991]
Explanation: 
Map the number 991 as follows:
1. mapping[9] = 6, so all occurrences of the digit 9 will become 6.
2. mapping[1] = 9, so all occurrences of the digit 1 will become 9.
Therefore, the mapped value of 991 is 669.
338 maps to 007, or 7 after removing the leading zeros.
38 maps to 07, which is also 7 after removing leading zeros.
Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38.
Thus, the sorted array is [338,38,991].
Copy the code

Note:

mapping.length == 10
0 <= mapping[i] <= 9
All the values of mapping[i] are unique.
1 <= nums.length <= 3 * 10^4
0 <= nums[i] < 10^9
Copy the code

parsing

Mapping [I] = j mapping[I] = j mapping[I] = j mapping[I] = j mapping[I] = j

Sort the integers in non-descending order based on the size of each element mapping. Note the following:

  • If the mapped values are the same, make sure they are in the same relative position as before
  • We are sorting the elements in NUMS, not mapping the elements in NUMS and then sorting them

We can use python’s built-in sorted function to sort nums. Then we can define a custom function to calculate the mapped value of each element. Nums can sort non-descending order according to this function. The idea is quite clear, the code is very simple.

There are at most 3 * 10^4 elements in NUMS, and each element is at most 10 digits. The time complexity calculated by mapping all elements is O(K * N), and then the time complexity calculated by sorting is O(NlogN). So the total time is O(K * N) + O(NlogN), and the space is O(N).

answer

class Solution(object):
    def sortJumbled(self, mapping, nums):
        """
        :type mapping: List[int]
        :type nums: List[int]
        :rtype: List[int]
        """
        def custom(x):
            if x==0: return mapping[0]
            result = 0
            p = 0
            while x > 0:
                t = x % 10
                result += mapping[t] * pow(10, p)
                x //= 10
                p += 1
            return result
        return sorted(nums, key=custom)  	      	
Copy the code

The results

66/66 Test cases passed. Status: Accepted Runtime: 1985 MS Memory Usage: 19.8 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation