[数组排序] 1122. 数组的相对排序

1. 题目链接

1122. 数组的相对排序 - 力扣（LeetCode）

---

2. 题目大意

描述：给定两个数组，arr1 和 arr2， arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

要求：对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

说明：

• 1≤arr1.length,arr2.length≤1000。
• 0≤arr1[i],arr2[i]≤1000。

---

3. 示例

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

---

4. 解题思路

因为元素值范围在 [0,1000]，所以可以使用计数排序的思路来解题。

1. 使用数组 count 统计 arr1 各个元素个数。
2. 遍历 arr2****** 数组，将对应元素num2 按照个数 count[num2] 添加到答案数组 ans 中，同时在 count 数组中减去对应个数。**
3. 然后在处理 count 中剩余元素，将 count 中大于 0 的元素下标依次添加到答案数组 ans 中。
4. 最后返回答案数组 ans。

---

5. 参考代码

class Solution {public int[] relativeSortArray(int[] arr1, int[] arr2) {int[] count = new int[1001];int[] sortArray = new int[arr1.length];int j = 0;for(int a1 : arr1){count[a1]++;}for(int a2 : arr2){while(count[a2] > 0){sortArray[j++] = a2;count[a2]--;}}for(int i = 0; i < count.length; i++){while(count[i] > 0){sortArray[j++] = i;count[i]--;}}return sortArray;}
}

---