题目
输入两个数组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;
}
}
