【LeeCode】1122. 数组的相对排序

【题目描述】

给你两个数组，​​arr1​​​ 和 ​​arr2​​​，​​arr2​​​ 中的元素各不相同，​​arr2​​​ 中的每个元素都出现在 ​​arr1​​ 中。

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

 ​​https://leetcode.cn/problems/relative-sort-array/​​

【示例】

【代码】admin

思路：根据arr1出现的次数, 叠加响应的次数即可

package com.company;
// 2023-03-17
import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 排序, 方便后面直接补位
        Arrays.sort(arr1);
        // 因为arr1包含arr2, 所以实际的大小就是arr1的长度
        int[] res = new int[arr1.length];
        // 统计arr1中每个数字出现的频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr1.length; i++){
            map.put(arr1[i], map.getOrDefault(arr1[i], 0) + 1);
        }
        int index = 0;
        // 方便后面排除元素是否在arr2中出现过
        List<Integer> list = new ArrayList<>();
        for (int x : arr2){
            if (map.containsKey(x)){
                int count = map.get(x);
                // x元素出现了count次,则添加count
                for (int k = 0; k < count; k++){
                    list.add(x);
                    res[index++] = x;
                }
            }
        }

        for (int xx : arr1){
            if (!list.contains(xx)){
                res[index++] = xx;
            }
        }
        System.out.println(Arrays.toString(res));
        return res;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().relativeSortArray(new int[]{2,3,1,3,2,4,6,7,9,2,19}, new int[]{2,1,4,3,9,6});   // 输出：[2,2,2,1,4,3,3,9,6,7,19]
        new Solution().relativeSortArray(new int[]{28,6,22,8,44,17}, new int[]{22,28,8,6});   // 输出：[22,28,8,6,17,44]
    }
}

【代码】计数排序

package com.company;
// 2023-03-17
import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] res = new int[1001];

        // 以arr1中的元素为下标, 出现的次数为值
        for (int x : arr1)
            res[x]++;

        // 新下标
        int index = 0;
        for (int y : arr2){
            // arr2中的元素在arrr1中出现了
            while (res[y] > 0){
                arr1[index++] = y;
                res[y]--;
            }
        }

        // 在arr2中未出现的元素
        // 注意：这里循环的是1001
        for (int i = 0; i < 1001; ++i){
            while (res[i]-- > 0){
                arr1[index++] = i;
            }
        }
        return arr1;
    }
}


public class Test {
    public static void main(String[] args) {
        new Solution().relativeSortArray(new int[]{2,3,1,3,2,4,6,7,9,2,19}, new int[]{2,1,4,3,9,6});   // 输出：[2,2,2,1,4,3,3,9,6,7,19]
//        new Solution().relativeSortArray(new int[]{28,6,22,8,44,17}, new int[]{22,28,8,6});   // 输出：[22,28,8,6,17,44]
    }
}