Sort the Jumbled Numbers

Leetcode Problem:

• Sort the Jumbled Numbers

Summary

• The problem requires sorting an array of integers based on their mapped values in a shuffled decimal system.

Approach

• The solution uses a modified merge sort algorithm to sort the array
• It first creates a temporary array to store the sorted elements, and then merges the sorted subarrays into the original array.

Complexity

• O(n log n)

Explain

• The solution defines a helper function `getNum` to calculate the mapped value of a given integer
• It then uses a modified merge sort algorithm to sort the array
• The `merge` function is used to merge two sorted subarrays into one, and the `merge_sort` function recursively divides the array into smaller subarrays and sorts them
• The sorted subarrays are then merged back into the original array using the `merge` function.

Solution Code:

class Solution {
public:
    int tmp[30001];
    int getNum(vector& mapping, int a){
        int pow = 1;
        int res = 0;
        if (a == 0) return mapping[a];
        while(a){
            res += (mapping[a%10])*pow;
            pow *= 10;
            a /= 10;
        }
        return res;
    }
    void merge(vector& mapping, vector& nums, int l, int mid, int r ){
        int i = l;
        int j = mid + 1;
        int cur = i;
        while(i <= mid && j <= r){
            if(getNum(mapping, nums[i]) <= getNum(mapping, nums[j])){
                tmp[cur++] = nums[i++];
            } else {
                tmp[cur++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = nums[i++];    
        }
        for(i = l ; i < cur; i++){
            nums[i] = tmp[i];
        }
    }
    void merge_sort(vector& mapping, vector& nums, int l, int r ){
        if (l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(mapping, nums, l, mid);
        merge_sort(mapping, nums, mid+1, r);
        merge(mapping, nums, l, mid, r);
    }
    vector sortJumbled(vector& mapping, vector& nums) {
        merge_sort(mapping, nums, 0, nums.size() - 1);
        return nums;
    }
};