Custom Compare and mapInt Function | C++, Python, Java
Approach\n Describe your approach to solving the problem. \nWe can make a list (or hashmap) of pairs where the first item is the mapped value, and the second it
# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can make a list (or hashmap) of pairs where the first item is the mapped value, and the second item is index of the current value. We can also define a function that creates our mapped valus for us `mapInt`. \n\n**mapInt function:** `pos` represents the position of the current digit in the result. In each iteration we take the mapped value for the last digit `n % 10`, multiply it by `pos` then add it to res. This computes the correct positional value of each mapped digit. Then we update `pos` by multiplying it by 10 to move to the next position, and dividing `n` by 10 to remove the last digit.\n\nIf using a list of pairs, we can sort the array without a compare function if the default sorting is in increasing order, because it will first sort by their values, but if they are equal, it will sort by the indices in increasing order, resulting in the relative order being maintained. You will just need to create a separate array/list for the result since you can\'t create the array with `nums` while modifying it then add all the values using the second item (index) for each pair.\n\nIf using a hashmap, you can map each value in `nums` to a pair in the form of (mappedValue, index). This way, if you create a compare function, you can use the key-value pairs as the key for sorting (like in a lambda function in python).\n# Complexity\n- Time complexity: $$O(n(log(n)))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        vector<pair<int, int>> pairs; // Stores (mapped_value, index)\n        for (int i = 0; i < nums.size(); i++)\n            pairs.emplace_back(mapInt(nums[i], mapping), i);\n        sort(pairs.begin(), pairs.end()); // Sorts first by mapped_value then by index in ascending order\n        vector<int> res;\n        for (auto& pair : pairs)\n            res.push_back(nums[pair.second]); // Add the original value back into our result\n        return res;\n    }\nprivate:\n    int mapInt(int n, vector<int>& mapping){\n        if (n == 0)\n            return mapping[0];\n        int res = 0, pos = 1;\n        while (n > 0) {\n            res += mapping[n % 10] * 10;\n            n /= 10;\n        }\n        return res;\n    }\n};\n```\n```python []\nclass Solution:\n    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:\n        \n        def mapInt(n):\n            if not n:\n                return mapping[0]\n            res, pos = 0, 1\n            while n:\n                res += mapping[n % 10] * pos\n                pos *= 10\n                n //= 10\n            return res\n        # Creates a dictionary with n as the key and a tuple in the form (mapped_value, index)\n        pairs = {n : (mapInt(n), idx) for idx, n in enumerate(nums)}\n\n        return sorted(nums, key=lambda x: pairs[x]) # Our key for sorting is the tuple returned by the pairs dictionary\n```\n```Java []\nclass Solution {\n    public int[] sortJumbled(int[] mapping, int[] nums) {\n        int n = nums.length;\n        int[][] pairs = new int[n][2]; // 2D Array where pairs[i][0] = mapped_value\n        // and pairs[i][1] = index\n        for (int i = 0; i < n; i++){\n            pairs[i][0] = mapInt(nums[i], mapping);\n            pairs[i][1] = i;\n        }\n        Arrays.sort(pairs, (a, b) -> {\n            return a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]);\n        }); // Custom compare function that compares indices if mapped values are equal and the values themselves if they\'re not.\n        int[] res = new int[n];\n        for (int i = 0; i < n; i++)\n            res[i] = nums[pairs[i][1]];\n        return res;\n    }\n    private int mapInt(int n, int[] mapping) {\n        if (n == 0)\n            return mapping[0];\n        int res = 0, pos = 1;\n        while (n > 0) {\n            res += mapping[n % 10] * pos;\n            pos *= 10;\n            n /= 10;\n        }\n        return res;\n    }\n}\n\n```\n
['Array', 'C', 'Sorting', 'Python', 'C++', 'Java', 'Python3']