LeetCode 1122. 数组的相对排序 JAVA

偏执的太偏执、 2022-12-21 03:17 139阅读 0赞

给你两个数组，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
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
1、遍历arr1，利用TreeMap按照Key进行排序；  
2、遍历arr2，按照arr2的相对顺序对arr1进行排序；  
3、遍历TreeMap，对尚未排序的按照从小到大的顺序进行排序。

class Solution {
        
        public int[] relativeSortArray(int[] arr1, int[] arr2) {
        
            int len1=arr1.length;
            int len2=arr2.length;
            int []res=new int [len1];
            Map<Integer,Integer> map=new TreeMap<>();
            for(int arr:arr1){
        
                int cnt=map.getOrDefault(arr,0)+1;
                map.put(arr,cnt);
            }
            int j=0;
            for(int i=0;i<len2;i++){
        
                int cnt=map.get(arr2[i]);
                while(cnt!=0){
        
                    res[j++]=arr2[i];
                    cnt--;
                }
                //map.put(arr2[i],0);
                map.remove(arr2[i]);
            }
            for(Map.Entry<Integer,Integer> entry:map.entrySet()){
        
                int cnt=entry.getValue();
                while(cnt!=0){
        
                    res[j++]=entry.getKey();
                    cnt--;
                }
            }
            return res;
        }
    }