Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2191.html
2191. Sort the Jumbled Numbers (Medium)
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
numsshould 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] <= 9- All the values of
mapping[i]are unique. 1 <= nums.length <= 3 * 1040 <= nums[i] < 109
Companies:
Goldman Sachs
Related Topics:
Array, Sorting
Similar Questions:
Solution 1.
-
class Solution { public int[] sortJumbled(int[] mapping, int[] nums) { List<int[]> m = new ArrayList<>(); for (int i = 0; i < nums.length; ++i) { int v = nums[i]; int a = v, b = 0, t = 1; while (true) { int x = a % 10; x = mapping[x]; a /= 10; b = x * t + b; t *= 10; if (a == 0) { break; } } m.add(new int[] {b, i, v}); } m.sort((a, b) -> { if (a[0] != b[0]) { return a[0] - b[0]; } if (a[1] != b[1]) { return a[1] - b[1]; } return 0; }); for (int i = 0; i < m.size(); ++i) { nums[i] = m.get(i)[2]; } return nums; } } -
class Solution: def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]: m = [] for i, v in enumerate(nums): a, b, t = v, 0, 1 while 1: a, x = divmod(a, 10) x = mapping[x] b = x * t + b t *= 10 if a == 0: break m.append((b, i, v)) m.sort() for i, v in enumerate(m): nums[i] = v[2] return nums -
class Solution { public: vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) { int n = nums.size(); vector<pair<int, int>> arr(n); for (int i = 0; i < n; ++i) { int x = nums[i]; int y = x == 0 ? mapping[0] : 0; int k = 1; for (; x; x /= 10) { y += k * mapping[x % 10]; k *= 10; } arr[i] = {y, i}; } sort(arr.begin(), arr.end()); vector<int> ans; for (auto& [_, i] : arr) { ans.push_back(nums[i]); } return ans; } }; -
func sortJumbled(mapping []int, nums []int) (ans []int) { n := len(nums) arr := make([][2]int, n) for i, x := range nums { y := 0 if x == 0 { y = mapping[0] } k := 1 for ; x > 0; x /= 10 { y += k * mapping[x%10] k *= 10 } arr[i] = [2]int{y, i} } sort.Slice(arr, func(i, j int) bool { a, b := arr[i], arr[j] return a[0] < b[0] || a[0] == b[0] && a[1] < b[1] }) for _, x := range arr { ans = append(ans, nums[x[1]]) } return } -
function sortJumbled(mapping: number[], nums: number[]): number[] { const n = nums.length; const arr: number[][] = []; for (let i = 0; i < n; ++i) { let x = nums[i]; let y = x === 0 ? mapping[0] : 0; let k = 1; for (; x > 0; x = Math.floor(x / 10), k *= 10) { y += mapping[x % 10] * k; } arr.push([y, i]); } arr.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])); return arr.map(a => nums[a[1]]); }