[C++] Custom Sorting Solutions, ~75% Time (450ms), ~55% Space (91.6)
Nice problem, which basically boils down to converting numbers into another lexicographic order/system as provided by mapping.\n\nThe temptation might be to con
Nice problem, which basically boils down to converting numbers into another lexicographic order/system as provided by `mapping`.\n\nThe temptation might be to convert the numbers to strings or arrays and replace each character/digit and then make them into a new number again, but we can do better.\n\nFirst of all, let\'s start with a relatively naive implementation where  we will store all our conversions in a hashtape, `mapped`, properly sized to contain at least `nums.size()` elements.\n\nWe will then store the converted value of `n` into `mapped[n]` using `convert`.\n\nThis function is the core of our logic and it will take the original number `n`, the relevant `mapping` provided to each call of the new function and then:\n* if `n == 0`, just return `mapping[n]`;\n* alternatively, we will declare our support variables `res` and `p`, initially set to `0` and `1`, respectively;\n* we will then proceed while `n != 0` and:\n\t* assign the result of calling `div(n, 10)` to `tmp`, in order to save a bit of computation and get division and remainder into one;\n\t* increase the accumulator `res` by `mapping[tmp.rem] * p` (ie: parsing the current rightmost digit according to `mapping` and adding it in the right position in `res`);\n\t* decuplicate `p`;\n\t* shave off the recently used rightmost digit from `n`, setting it to be `tmp.quot`;\n* finally, we will `return` `res`.\n\nOnce done, we can just sort `nums` in place mapping directly to `mapped` and the game is done (no need to bother with stable sorting this way) :)\n\nThe code:\n\n```cpp\nclass Solution {\n    div_t tmp;\n    int convert(int n, const vector<int>& mapping) {\n        // edge case: n == 0\n        if (!n) return mapping[n];\n        // support variables\n        int res = 0, p = 1;\n        while (n) {\n            tmp = div(n, 10);\n            res += mapping[tmp.rem] * p;\n            p *= 10;\n            n = tmp.quot;\n        }\n        return res;\n    }\npublic:\n    vector<int> sortJumbled(const vector<int>& mapping, vector<int>& nums) {\n        // suppport variables\n        unordered_map<int, int> mapped;\n        // populating mapped\n        mapped.reserve(nums.size());\n        for (int n: nums) mapped[n] = convert(n, mapping);\n        // sorting by mapped values\n        sort(begin(nums), end(nums), [&](int a, int b){\n            return mapped[a] < mapped[b];\n        });\n        return nums;\n    }\n};\n```\n\nSome other attempts using an extra container to store the converted numbers directly with their original index and value:\n\n```cpp\nconstexpr int m[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};\n\nclass Solution {\n    int convert(int n, const vector<int>& mapping) {\n        // edge case: n == 0\n        if (!n) return mapping[n];\n        // support variables\n        int res = 0, p = 0;\n        while (n) {\n            res += mapping[n % 10] * m[p];\n            p++;\n            n /= 10;\n        }\n        return res;\n    }\npublic:\n    vector<int> sortJumbled(const vector<int>& mapping, vector<int>& nums) {\n        // suppport variables\n        int len = nums.size();\n        vector<int> mapped[len];\n        // populating mapped\n        for (int i = 0; i < len; i++) {\n            mapped[i] = {convert(nums[i], mapping), nums[i]};\n        }\n        // sorting by mapped values\n        stable_sort(mapped, mapped + len, [](auto &a, auto &b){return a[0] < b[0];});\n        for (int i = 0; i < len; i++) nums[i] = mapped[i][1];\n        return nums;\n    }\n};\n```\n\nThis one is basically the same, but without custom comparison and faster - for some reason:\n\n```cpp\nconstexpr int m[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};\n\nclass Solution {\n    int convert(int n, const vector<int>& mapping) {\n        // edge case: n == 0\n        if (!n) return mapping[n];\n        // support variables\n        int res = 0, p = 0;\n        while (n) {\n            res += mapping[n % 10] * m[p];\n            p++;\n            n /= 10;\n        }\n        return res;\n    }\npublic:\n    vector<int> sortJumbled(const vector<int>& mapping, vector<int>& nums) {\n        // suppport variables\n        int len = nums.size();\n        vector<int> mapped[len];\n        // populating mapped\n        for (int i = 0; i < len; i++) {\n            mapped[i] = {convert(nums[i], mapping), i, nums[i]};\n        }\n        // sorting by mapped values\n        stable_sort(mapped, mapped + len);\n        for (int i = 0; i < len; i++) nums[i] = mapped[i][2];\n        return nums;\n    }\n};\n```
['C', 'Sorting', 'C++']