数组的相对排序

发表于
本文字数： 4k 阅读时长 ≈ 4 分钟

LeetCode每日一题，1122. Relative Sort Array

先看题目描述

D9xuvR.png

大意就是有两个数组 arr2 和 arr1，arr2 中没有重复数字，让我们对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾

算法和思路

重写排序规则

由于数组 arr 2 规定了比较顺序，因此我们可以使用哈希表对该顺序进行映射：即对于数组 arr2 中的第 i 个元素，我们将 (arr2[i], i) 这一键值对放入哈希表 map 中，就可以很方便地对数组 arr1 中的元素进行比较

然后就重写排序规则就可以：

  • 若 x 和 y 都在哈希表中，则对应值较大的那个排后面
  • 若 x 和 y 都不在哈希表中，则本身值较大的那个排后面
  • 其他情况下，则不在哈希表中的那个排后面

计数排序

具体地，我们使用一个长度为1 001（下标从 0 到 1000）的数组 counts，记录每一个元素在数组 arr1 中出现的次数。随后我们遍历数 arr2，当遍历到元素 x 时，我们将 counts[x] 个 x 加入答案中，并将 counts[x] 清零。当遍历结束后，arr2 中出现过的元素就已经有序了。

对于剩下的没在 arr2 中出现过的元素，我们只需再遍历一次数组 counts，当遍历到 counts[x] > 0 时，将 counts[x] 个 x 添加到 ans 数组后面。当遍历结束后，没在 arr2 中出现过的元素已按照升序排列在 ans 数组最后，返回 ans 数组即可

算法源码

重写排序规则

由于 java 中的 Arrays.sort() 不能对 int 数组重写排序规则，所有得先把数组转化为列表，再按新的规则排序，然后再把 list 转回数组并返回，操作比较耗时，运行效率不高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;

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

计数排序

下面是自己一开始实现的计数排序代码，由于没想到可以在遍历 arr2 时把 counts[x] 清零的操作，所以在最后遍历 counts 数组时使用了一个 HashSet 来判断元素是否出现在 arr2 中，效率比采取清零操作的代码会低一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int m = arr1.length;
        int n = arr2.length;
        int[] ans = new int[m];
        int[] counts = new int[1001];
        Set<Integer> nums = new HashSet<>();
        for (int num : arr2) {
            nums.add(num);
        }
        for (int num : arr1) {
            counts[num]++;
        }
        int index = 0;
        for (int i = 0; i < n; i++) {
            int num = arr2[i];
            for (int j = 0; j < counts[num]; j++) {
                ans[index] = num;
                index++;
            }
        }
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0 && !nums.contains(i)) {
                for (int j = 0; j < counts[i]; j++) {
                    ans[index] = i;
                    index++;
                }
            }
        }
        return ans;
    }
}

下面是在遍历数组 arr2 时使用了清零操作的代码，事实上这个算法的空间复杂度还可以优化，这里定义的 counts 数组长度是 1001，我们可以找出 arr1 数组中元素的最大值 max，然后定义 counts 数组的长度为 max + 1（下标为 0 到 max）即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int m = arr1.length;
        int n = arr2.length;
        int[] ans = new int[m];
        int[] counts = new int[1001];
        for (int num : arr1) {
            counts[num]++;
        }
        int index = 0;
        for (int i = 0; i < n; i++) {
            int num = arr2[i];
            for (int j = 0; j < counts[num]; j++) {
                ans[index] = num;
                index++;
            }
            counts[num] = 0;
        }
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0) {
                for (int j = 0; j < counts[i]; j++) {
                    ans[index] = i;
                    index++;
                }
            }
        }
        return ans;
    }
}