Given two integer arrays A1 and A2, sort A1 in such a way that the relative order among the elements will be same as those are in A2.

For the elements that are not in A2, append them in the right end of the A1 in an ascending order.

Assumptions:

• A1 and A2 are both not null.
• There are no duplicate elements in A2.

Examples:

• A1 = {2, 1, 2, 5, 7, 1, 9, 3}, A2 = {2, 1, 3}, A1 is sorted to {2, 2, 1, 1, 3, 5, 7, 9}

Solution: Comparator + HashMap。Comparator里的hashmap加入A2(key = num, val = index)，比较时，若2个元素都在hashmap，则按照index顺序；若2个元素都不在hashmap，按元素大小

  public int[] sortSpecial(int[] A1, int[] A2) {
    Integer[] a1 = toIntegerArray(A1);
    //注意Arrays.sort若要用comparator，则不能用primitive array
    Arrays.sort(a1, new MyComparator(A2));
    toIntArray(A1, a1);
    return A1;
  }

  class MyComparator implements Comparator<Integer>{
    private Map<Integer, Integer> map;
    public MyComparator(int[] array) {
      map = new HashMap<>();
      for (int i = 0; i < array.length; i++) {
        map.put(array[i], i);
      }
    }
    @Override
    public int compare(Integer a, Integer b) {
      Integer index_a = map.get(a);
      Integer index_b = map.get(b);
      if (index_a != null && index_b != null) {
        return index_a.compareTo(index_b);
      }
      if (index_a == null && index_b == null) {
        return a.compareTo(b);
      }
      return index_a != null ? -1 : 1;
    }
  }

  private Integer[] toIntegerArray(int[] a) {
    Integer[] ans = new Integer[a.length];
    for (int i = 0; i < ans.length; i++) {
      ans[i] = a[i];
    }
    return ans;
  }
  private void toIntArray(int[] ans, Integer[] a) {
    for (int i = 0; i < ans.length; i++) {
      ans[i] = a[i];
    }
  }