Sort pairs (mapping(x), index) vs Sort with lambda->1 line||80ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nSeveral approaches.\nAll of solutions need to define convert(x, mapping) from the given
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSeveral approaches.\nAll of solutions need to define convert(x, mapping) from the given mapping.\nPython 1-liner is also provided.\n\n**Sort with lambda or custom comparator has no info on indices, should use stable_sort!! std::sort is an unstable sort, the terms with same mapped values might not keep the relative order!!!!** And Python built-in sorted() function is guaranteed to be stable. [docs.python.org](https://docs.python.org/3/library/functions.html#sorted)\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on english subtitles if necessary]\n[https://youtu.be/IBzi6LbqCXE?si=-8HUO1rdGiy9pQDs](https://youtu.be/IBzi6LbqCXE?si=-8HUO1rdGiy9pQDs)\n1. Define the function `int convert(int x, vector<int>& mapping)` to map x to the corresponding number w.r.t. `mapping`. Be careful when x=0 the edge case.\n2. 1st approach uses a container `mapNum` holding the info tuples `(mapping nums, idx, x)`\n3. Sort `mapNum`\n4. Rebuild `nums` by setting `nums[i]=mapNum[i][2]` for each i\n5. 2nd approach is  to define the lambda `[&](int x, int y){\n            return f[x]<f[y];\n        });` in the std::stable_sort for which f is an unorderered_map using `convert` & slow but accepted\n6. 3rd approach is a variant for 1st one using sorting pairs `(mapping num, idx)`; for the answering it needs an extra container `ans`.\n7. 4th C++ usues packing of  `(mapping num, idx)` to an int64, then sort & unpack which is the fastest one.\n8.  Python 1-line is made; the convert part uses string.\n9. C++ stable_sort idx with lambda+ array f given by mapping which is also fast. It should be noted that sort with lambda should have  an easy comparator at best only O(1) computing time, otherwise it should be a look-up table for precalculation.\n# Least Significant Digit First convert(x, mapping)\nSince it doesn\'t convert x to the string, & just dealing with ints, in contray to the method by using string, the algorithm uses sucessive divisions with remainder & goes from the least signifcant digit up. The Python code for that is as follows:\n```\ndef convert(x):\n    if x==0: return mapping[0] # edge case\n    z=0 \n    pow10=1\n    while x>0:\n        q, r=divmod(x, 10) # division with remainder\n        z+=mapping[r]*pow10 # Use mapping\n        x=q\n        pow10*=10\n    return z\n```\n# comparison among several methods\n|Method|Elapsed time|Record| Memory|\n|---|---|---|---|\n|C++ Sort tuples|124ms|97.40%|82.21MB|\n|C++ stable_sort with lambda+hash table as look-up table|651ms|19.05%|96.12MB|\n|C++ Sort pairs|82ms|100%|80.44MB|\n|C++ Sort packing pairs into int64s then unpack|80ms| 100%|80.44MB|\n|C++ stable_sort idx with lambda+ array as look-up table|98ms|100%|79.41MB|\n|Python Sort tuples|1002ms|69.56%|25.27MB|\n|Python 1-liner|868ms|88.59%|22.95MB\n# Testcase for sort with lambda failing\nWhen sorting using lambda or custom comparator, it would not pass the following testcase & should use stable_sort. The testcase is provided by @stephen_byerley\n```\n[8,9,4,0,2,1,3,5,7,6]\n[991,338,38,33338,33333338,338,333338,3333338,333333338,33333338,338,33333338,33338,33338,33333338,333333338,38]\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n\\log n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n# Code Sort tuple (mapping(x), index, x) ||C++ 124 ms Beats 97.40%\n```C++ []\nclass Solution {\npublic:\n    using int3=array<int, 3>;\n    static int convert(int x, vector<int>& mapping){\n        if (x==0) return mapping[0];//  edge case\n        int z=0;\n        for(int pow10=1; x>0; pow10*=10){\n            auto [q, r]=div(x, 10);\n            z+=mapping[r]*pow10;\n            x=q;\n        }\n        return z;\n    }\n\n    static vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        const int n=nums.size();\n        vector<int3> mapNum(n);\n        for(int i=0; i<n; i++){\n            int x=nums[i];\n            mapNum[i]={convert(x, mapping),i,  x};//(mapping nums, idx, x)\n        }\n        sort(mapNum.begin(), mapNum.end());// Use default sort is better\n        for(int i=0; i<n; i++)\n            nums[i]=mapNum[i][2];\n        return nums;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n```Python []\nclass Solution:\n    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:\n        def convert(x):\n            if x==0: return mapping[0]\n            z=0\n            pow10=1\n            while x>0:\n                q, r=divmod(x, 10)\n                z+=mapping[r]*pow10\n                x=q\n                pow10*=10\n            return z\n        n=len(nums)\n        mapNum=[]\n        for i, x in enumerate(nums):\n            mapNum.append([convert(x), i, x])\n        mapNum.sort()\n        for i in range(n):\n            nums[i]=mapNum[i][2]\n        return nums\n        \n        \n```\n# stable_sort with lambda which is slow but accepted||651ms\n```\nclass Solution {\npublic:\n    static int convert(int x, vector<int>& mapping){\n        if (x==0) return mapping[0];//  edge case\n        int z=0;\n        for(int pow10=1; x>0; pow10*=10){\n            auto [q, r]=div(x, 10);\n            z+=mapping[r]*pow10;\n            x=q;\n        }\n        return z;\n    }\n\n    static vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        const int n=nums.size();\n        unordered_map<int, int> f;\n        f.reserve(n);\n        for(int i=0; i<n; i++) \n            f[nums[i]]=convert(nums[i], mapping);\n\n        stable_sort(nums.begin(), nums.end(), [&](int x, int y){\n            return f[x]<f[y];\n        });\n        return nums;\n    }\n};  \n```\n# C++ sort pairs (mapping x, index)||0ms beats 100%\n[See submission](https://leetcode.com/problems/sort-the-jumbled-numbers/submissions/1331268299/)\n```\nclass Solution {\npublic:\n    using int2=array<int, 2>;\n    static int convert(int x, vector<int>& mapping){\n        if (x==0) return mapping[0];//  edge case\n        int z=0;\n        for(int pow10=1; x>0; pow10*=10){\n            auto [q, r]=div(x, 10);\n            z+=mapping[r]*pow10;\n            x=q;\n        }\n        return z;\n    }\n\n    static vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        const int n=nums.size();\n        vector<int2> mapNum(n);\n        for(int i=0; i<n; i++){\n            int x=nums[i];\n            mapNum[i]={convert(x, mapping),i};//(mapping nums, idx)\n        }\n        sort(mapNum.begin(), mapNum.end());// Use default sort is better\n        vector<int> ans(n);\n        for(int i=0; i<n; i++)\n            ans[i]=nums[mapNum[i][1]];\n        return ans;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# C++ packs pairs into int64s then unpack|80ms beats 100%\n```\nclass Solution {\npublic:\n    static int convert(int x, vector<int>& mapping){\n        if (x==0) return mapping[0];//  edge case\n        int z=0;\n        for(int pow10=1; x>0; pow10*=10){\n            auto [q, r]=div(x, 10);\n            z+=mapping[r]*pow10;\n            x=q;\n        }\n        return z;\n    }\n\n    static vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        const int n=nums.size();\n        vector<long long> mapNum(n);\n        for(int i=0; i<n; i++){\n            int x=nums[i];\n            mapNum[i]=((long long)convert(x, mapping)<<32)+i;//(mapping nums, idx)\n        }\n        sort(mapNum.begin(), mapNum.end());// Use default sort is better\n        vector<int> ans(n);\n        for(int i=0; i<n; i++)\n            ans[i]=nums[mapNum[i]& 0xffffffff];//unpack\n        return ans;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# Python 1-liner\n```\nclass Solution:\n    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:\n        return sorted(nums, key=lambda x: int("".join(chr(mapping[ord(c)-48]+48) for c in str(x))))\n\n```\n# C++ stable_sort idx with lambda+ array as look-up table|98ms beats 100%\n```\nclass Solution {\npublic:\n    static int convert(int x, vector<int>& mapping){\n        if (x==0) return mapping[0];//  edge case\n        int z=0;\n        for(int pow10=1; x>0; pow10*=10){\n            auto [q, r]=div(x, 10);\n            z+=mapping[r]*pow10;\n            x=q;\n        }\n        return z;\n    }\n\n    static vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        const int n=nums.size();\n        vector<int> idx(n), f(n);\n        iota(idx.begin(), idx.end(), 0);\n        for(int i=0; i<n; i++) \n            f[i]=convert(nums[i], mapping);\n            \n        stable_sort(idx.begin(), idx.end(), [&](int x, int y){\n            return f[x] < f[y];\n        });\n        vector<int> ans(n);\n        for(int i=0; i<n; i++)\n            ans[i]=nums[idx[i]];\n        return ans;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Array', 'Hash Table', 'Bit Manipulation', 'Sorting', 'C++', 'Python3']