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