[数据结构与算法]数组相对排序

https://leetcode-cn.com/problems/0H97ZC/

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //计数排序

        int upper = 0;
        for (int i : arr1) {
            upper = Math.max(upper, i);
        }

        int[] frq = new int[upper + 1];

        //数组1中每个元素的频率，下标即对应的元素
        for (int i : arr1) {
            ++ frq[i];
        }
        
        //一个新数组存取结果，因为arr2长度小于等于arr1长度
        int[] ans = new int[arr1.length];
        int id = 0;
        
        //遍历arr2
        for (int i : arr2) {
            //因为是要让arr1按照arr2的顺序进行存放，frq数组记录的是频率，也就是有几个对应的数
            for (int j = 0; j < frq[i]; j ++) {
                ans[id++] = i;
            }
            //存放过后的数，频率清零，为了处理arr1中arr2中未出现的元素
            frq[i] = 0;
        }

        //处理arr2中未出现的元素
        for (int i = 0; i <= upper; ++ i) {
            for (int j = 0; j < frq[i]; ++ j) {
                ans[id ++] = i;
            }
        }
        return ans;
    }
}