Leetcode

Sort the Jumbled Numbers

May 26, 2022 by aAshish

Approach 1: Sort

  • Time:O(n\log n)
  • Space:O(n)

C++

 
class Solution {
 public:
  vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
    vector<int> ans;
    vector<tuple<int, int, int>> A;  // (mapped, index, num)

    for (int i = 0; i < nums.size(); ++i)
      A.emplace_back(getMapped(nums[i], mapping), i, nums[i]);

    sort(begin(A), end(A));

    for (const auto& [_, i, num] : A)
      ans.push_back(num);

    return ans;
  }

 private:
  int getMapped(int num, const vector<int>& mapping) {
    string mapped;
    for (const char c : to_string(num))
      mapped += to_string(mapping[c - '0']);
    return stoi(mapped);
  }
};

JAVA

 
class Solution {
  public int[] sortJumbled(int[] mapping, int[] nums) {
    int[] ans = new int[nums.length];
    List<int[]> A = new ArrayList<>(); // (mapped, index, num)

    for (int i = 0; i < nums.length; ++i)
      A.add(new int[] {getMapped(nums[i], mapping), i, nums[i]});

    Collections.sort(A, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    return A.stream().mapToInt(a -> a[2]).toArray();
  }

  private int getMapped(int num, int[] mapping) {
    StringBuilder sb = new StringBuilder();
    for (final char c : String.valueOf(num).toCharArray())
      sb.append(mapping[c - '0']);
    return Integer.parseInt(sb.toString());
  }
}

Python

 
class Solution:
  def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
    def getMapped(num: int) -> int:
      mapped = []
      for c in str(num):
        mapped.append(str(mapping[ord(c) - ord('0')]))
      return int(''.join(mapped))
    A = [(getMapped(num), i, num) for i, num in enumerate(nums)]
    return [num for _, i, num in sorted(A)]

Approach 2: Ordered Map

  • Time:O(n\log n)
  • Space:O(n)

C++

 
class Solution {
 public:
  vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
    vector<int> ans;
    map<int, vector<int>> mappedToOriginalNums;

    for (const int num : nums)
      mappedToOriginalNums[getMapped(num, mapping)].push_back(num);

    for (const auto& [_, originalNums] : mappedToOriginalNums)
      ans.insert(end(ans), begin(originalNums), end(originalNums));

    return ans;
  }

 private:
  int getMapped(int num, const vector<int>& mapping) {
    string mapped;
    for (const char c : to_string(num))
      mapped += to_string(mapping[c - '0']);
    return stoi(mapped);
  }
};

JAVA

 
class Solution {
  public int[] sortJumbled(int[] mapping, int[] nums) {
    List<Integer> ans = new ArrayList<>();
    TreeMap<Integer, List<Integer>> mappedToOriginalNums = new TreeMap<>();

    for (final int num : nums) {
      final int mapped = getMapped(num, mapping);
      mappedToOriginalNums.putIfAbsent(mapped, new ArrayList<>());
      mappedToOriginalNums.get(mapped).add(num);
    }

    for (var originalNums : mappedToOriginalNums.values())
      ans.addAll(originalNums);

    return ans.stream().mapToInt(i -> i).toArray();
  }

  private int getMapped(int num, int[] mapping) {
    StringBuilder sb = new StringBuilder();
    for (final char c : String.valueOf(num).toCharArray())
      sb.append(mapping[c - '0']);
    return Integer.parseInt(sb.toString());
  }
}