题目复述：
给你两个数组，arr1 和 arr2，
- arr2 中的元素各不相同
- arr2 中的每个元素都出现在 arr1 中
- 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：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.length, arr2.length <= 1000
- 0 <= arr1[i], arr2[i] <= 1000
- arr2 中的元素 arr2[i] 各不相同
- arr2 中的每个元素 arr2[i] 都出现在 arr1 中
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/relative-sort-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
先说一下我的思路吧：
- 首先创建两个存放整数的集合list和list2
- 再创建一个长度为arr1.length的数组num
- 外循环arr2，内循环arr1，找出所有arr2中与arr1中元素相同的元素并依次放进集合list中，此时list集合中的元素就是已经按照arr2中元素顺序排好了；
- 然后求出arr1数组和list集合长度的差值len，分为两种情况，第一种情况len为0；第二种情况len不为0；
- （1）len=0；直接将list集合赋值给数组num然后返回数组num即可
- （2）len!=0；找出剩余的元素放进集合list2中，顺便对list2排序，然后把list2的元素放进list中，最后把list赋值给num数组，返回即可。
代码可能有点长，不过划分为几块理解，还是很容易懂的
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
List<Integer> list = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
int[] num = new int[arr1.length];
int i = 0,j = 0;
for(i=0;i<arr2.length;i++){
for(j=0;j<arr1.length;j++){
if(arr2[i]==arr1[j]){
list.add(arr2[i]);
}
}
}
i=0;
int len = arr1.length - list.size();
if(len==0){
for(int item : list){
num[i++] = item;
}
return num;
}
else{
for(i=0;i<arr1.length;i++){
if(!list.contains(arr1[i])){
list2.add(arr1[i]);
}
}
Collections.sort(list2);
for(int item : list2){
list.add(item);
}
i = 0;
for(int item : list){
num[i++] = item;
}
}
return num;
}
}
接下来的解法可能没有上述方法好理解，小白也很难想到，但是比上边要厉害一些
理解的时候在草稿纸上自己动手写一写也很易懂，可以去看看桶排序帮助理解
Show The Code
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] m = new int[1001];
int[] ref = new int[arr1.length];
for(int i = 0; i < arr1.length; i++) {
m[arr1[i]]++;
}
int cnt = 0;
for(int i = 0; i < arr2.length; i++) {
while(m[arr2[i]] > 0) {
ref[cnt++] = arr2[i];
m[arr2[i]]--;
}
}
for(int i = 0; i < 1001; i++) {
while(m[i] > 0) {
ref[cnt++] = i;
m[i]--;
}
}
return ref;
}
}
主要思路：
- 遍历arr1数组，将arr1中的元素依次作为m数组的下标，对应m数组中的元素存储的是当前下标在arr1中出现的次数，比如m[2]=3就是说在arr1数组中，元素2出现了3次；
- 遍历arr2数组，因为是顺序遍历的，所以同时保证了ref中元素的顺序是和arr2中元素出现的顺序是一致的，m[2],m[1],m[4],m[3]....遍历的同时赋值给ref数组，注意分清楚下标和数组值之间的关系，m[arr2[i]]控制的是赋值的次数，arr2[i]是控制的赋值的值本身
- 最后找到剩余未出现在arr2中但是出现在了arr1中元素，按照顺序赋值给ref数组即可
理解的关键一定要自己动手！！！
最后来张美图！！
早点睡觉
