/**
 * Description: 数组的相对位置
 * 使用计数排序实现
 * Date: 2020-12-27
 * Time: 10:54 AM
 */
public class RelativeSortArray {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {

        //初始化计数桶
        int[] bucket = new int[1001];
        for (int num1 : arr1) {
            bucket[num1]++;
        }

        //按照arr2的相对顺序按照计数排序的规则来进行排序
        int idx = 0;
        for (int num2 : arr2) {
            while (bucket[num2] > 0) {
                arr1[idx++] = num2;
                bucket[num2]--;
            }
        }

        //将剩余的数放在arr1的末尾
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i] > 0) {
                arr1[idx++] = i;
                bucket[i]--;
            }
        }

        return arr1;

    }

    public static void main(String[] args) {

        int[] arr1 = new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
        int[] arr2 = new int[]{2, 1, 4, 3, 9, 6};

        System.out.println(new RelativeSortArray().relativeSortArray(arr1, arr2));
    }
}