面试算法75：数组相对排序

题目

输入两个数组arr1和arr2，其中数组arr2中的每个数字都唯一，并且都是数组arr1中的数字。请将数组arr1中的数字按照数组arr2中的数字的相对顺序排序。如果数组arr1中的数字在数组arr2中没有出现，那么将这些数字按递增的顺序排在后面。假设数组中的所有数字都在0到1000的范围内。例如，输入的数组arr1和arr2分别是[2，3，3，7，3，9，2，1，7，2]和[3，2，1]，则数组arr1排序之后为[3，3，3，2，2，2，1，7，7，9]。

分析

题目明确提出数组中的数字都在0到1000的范围内。这是一个很明显的提示，据此可以考虑采用计数排序。先统计数组[2，3，3，7，3，9，2，1，7，2]中每个数字出现的次数，发现数字1出现了1次，2出现了3次，3出现了3次，7出现了2次，以及9出现了1次。接下来根据数组[3，2，1]确定的数字顺序，先后输出3个3、3个2、1个1。由于还剩下数字7和9，因此再按照大小输出2个7和1个9。

解

public class Test {
    public static void main(String[] args) {
        int[] arr1 = {2, 3, 3, 7, 3, 9, 2, 1, 7, 2};
        int[] arr2 = {3, 2, 1};
        int[] result = relativeSortArray(arr1, arr2);
        for (int item : result) {
            System.out.println(item);
        }
    }

    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] counts = new int[1001];
        for (int num : arr1) {
            counts[num]++;
        }

        int i = 0;
        for (int num : arr2) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num]--;
            }
        }

        for (int num = 0; num < counts.length; num++) {
            while (counts[num] > 0) {
                arr1[i++] = num;
                counts[num]--;
            }
        }
        return arr1;
    }
}