【算法篇】_数组相对排序

数组相对排序

给定两个数组，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]

提示：

• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2 中的元素 arr2[i] 各不相同
• arr2 中的每个元素 arr2[i] 都出现在 arr1 中

解题思路

• 标签：统计出现频率
• 本题目因为要给两个数组进行相对排序，可对arr1中的元素做一个统计，然后按照arr2的顺序进行填充。

利用数组统计频率

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //统计各元素出现次数
        int[] res = new int[1001];
      for(int num:arr1){
          res[num]++;
      }
        int index = 0;
        //遍历 arr2，以 arr2的顺序填arr1数组
     for(int num:arr2){
         for(int i=0;i<res[num];i++){
             arr1[index++]=num;
         }
         res[num]=0;
     }
        //将剩下的数字按序填入arr1

for(int i=0;i<res.length;i++){
    for(int j=0;j<res[i];j++){
        arr1[index++]=i;
    }
}
        return arr1;
    }
}

利用treeMap

treeMap排序是根据字典顺序，而非插入顺序

 class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
		 Map<Integer,Integer> resMap = new TreeMap<>();
        for (int num:arr1){
            resMap.put(num,resMap.getOrDefault(num,0)+1);
        }
        int index=0;
        for (int num:arr2){
            for (int i=0;i<resMap.get(num);i++){
                arr1[index++]=num;
            }
            resMap.put(num,0);
        }
        for (Map.Entry<Integer, Integer> entry : resMap.entrySet()) {
           if (entry.getValue()>0) {
                System.out.println(resMap.get(entry.getKey()));
                arr1[index++] = entry.getKey();
                resMap.put(entry.getKey(),0);
            }
        }
        return arr1;
    }
}