1
class Solution {
2
  public int[] relativeSortArray(int[] arr1, int[] arr2) {
3
    Map<Integer, Integer> map = new TreeMap();
4
    for (int i = 0; i < arr1.length; i++) {
5
      if (map.containsKey(arr1[i])) {
6
        map.replace(arr1[i], map.get(arr1[i]), map.get(arr1[i]) + 1);
7
      } else {
8
        map.put(arr1[i], 1);
9
      }
10
    }
11

12
    int[] arr = new int[arr1.length];
13
    int ind = 0;
14
    for (int i = 0; i < arr2.length; i++) {
15

16
      for (int j = 0; j < map.get(arr2[i]); j++) {
17
        arr[ind] = arr2[i];
18
        ind++;
19
      }
20
      map.remove(arr2[i]);
21
    }
22

23
    for (int i : map.keySet()) {
24

25
      for (int j = 0; j < map.get(i); j++) {
26
        arr[ind] = i;
27
        ind++;
28
      }
29
    }
30

31
    return arr;
32
  }
33
}