1122. 数组的相对排序

本文主要是介绍1122. 数组的相对排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给你两个数组，arr1 和 arr2，

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/relative-sort-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

计数排序

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] cnt = new int[1001];
        for (int item : arr1) {
            cnt[item]++;
        }

        int[] ans = new int[arr1.length];

        int index = 0;
        for (int i = 0; i < arr2.length; ++i) {
            while (cnt[arr2[i]]-- > 0) {
                ans[index++] = arr2[i];
            }
        }

        for (int i = 0; i <= 1000; ++i) {
            while (cnt[i]-- > 0) {
                ans[index++] = i;
            }
        }
        return ans;
    }
}

自定义排序

import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int num : arr1) {
            list.add(num);
        }
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], i);
        }
        Collections.sort(list, (x, y) -> {
            if (map.containsKey(x) || map.containsKey(y)) {
                return map.getOrDefault(x, 1001) - map.getOrDefault(y, 1001);
            }
            return x - y;
        });
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = list.get(i);
        }
        return arr1;
    }
}

这篇关于1122. 数组的相对排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！