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:
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].
Example 2:
Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123] Output: [123,456,789] Explanation: 789 maps to 789, 456 maps to 456, and 123 maps to 123. Thus, the sorted array is [123,456,789].
Constraints:
mapping.length == 100 <= mapping[i] <= 9mapping[i] are unique.1 <= nums.length <= 3 * 1040 <= nums[i] < 109Explanation: To sort the numbers in 'nums' according to their mapped values, we'll first calculate the mapped value for each number. We can achieve this by creating a helper function that translates each digit using the given 'mapping' array. Then, we can pair each original number with its mapped value as tuples and sort these tuples based on the mapped values. This ensures that the relative order is maintained for numbers with the same mapped value.
The code defines a function mapped_value that converts a given number into its mapped equivalent using the 'mapping' array. We iterate through each number in 'nums', pair it with its mapped value, and sort these pairs based on the mapped values (using a lambda function as the key for sorting). Finally, we extract and return just the numbers in their new order.
JavaScript
Time Complexity: O(n * k log k), where n is the number of elements in 'nums' and k is the average number of digits in the numbers. This complexity arises from mapping each digit (O(k)) and sorting (O(n log n)).
Space Complexity: O(n) for storing the tuples of numbers and their mapped values.
Explanation: Instead of creating tuples, we can use a custom comparator function directly in our sort operation. This comparator will determine the order based on mapped values of numbers. By transforming the comparator function, we ensure in-place sorting, minimizing additional memory usage.
In this C++ solution, the mappedValue function calculates the mapped equivalent of a number using the 'mapping'. The comparator for the std::sort uses this mapped value to sort the numbers in-place. The syntax makes use of C++ lambda functions for inline declaration of comparator logic.
Java
Time Complexity: O(n * k log k), where n is the number of numbers and k is the average number of digits in the numbers due to the sorting and mapping logic. Space Complexity: O(1) additional in-place space.
| Approach | Complexity |
|---|---|
| Approach 1: Mapping and Sorting Using Tuples | Time Complexity: O(n * k log k), where n is the number of elements in 'nums' and k is the average number of digits in the numbers. This complexity arises from mapping each digit (O(k)) and sorting (O(n log n)). |
| Approach 2: In-place Reordering Using Custom Comparator | Time Complexity: O(n * k log k), where n is the number of numbers and k is the average number of digits in the numbers due to the sorting and mapping logic. Space Complexity: O(1) additional in-place space. |
Sort the Jumbled Numbers - Leetcode 2191 - Python • NeetCodeIO • 8,308 views views
Watch 9 more video solutions →Practice Sort the Jumbled Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor