数组的相对排序

难度: Easy

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

注意：本题与主站 1122 题相同：https://leetcode-cn.com/problems/relative-sort-array/

Submission

运行时间: 15 ms

内存: 16.0 MB

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # 哈希表中存储arr2数组中规定的比较顺序
        # rank = {}
        # for i in range(len(arr2)):
        #     rank[arr2[i]] = i

        # # 冒泡排序
        # for i in range(1, len(arr1)):
        #     for j in range(i, 0, -1):
        #         x, y = arr1[j - 1], arr1[j]
        #         if (x in rank and y in rank and rank[x] > rank[y]) or\
        #            (x not in rank and y not in rank and x > y) or\
        #            (x not in rank and y in rank):
        #             # 交换arr1[i - 1]和arr1[i]的位置
        #             temp = arr1[j - 1]
        #             arr1[j - 1] = arr1[j]
        #             arr1[j] = temp
            
        # return arr1

        # def mycmp(x):
        #     return rank[x] if x in rank else  x
        
        # n = len(arr2)
        # rank = {x:i - n for i, x in enumerate(arr2)}
        # arr1.sort(key=mycmp)

        # return arr1



        # 计数排序
        frenquency = [0] * (max(arr1) + 1)
        ans = []

        for item in arr1:
            frenquency[item] += 1

        for num in arr2:
            if frenquency[num] != 0:
                ans.extend([num] * frenquency[num])
                frenquency[num] = 0
        
        for i, item in enumerate(frenquency):
            if item != 0:
                ans.extend([i] * item)
        
        return ans

Explain

题解采用了计数排序的方法。首先创建一个频率数组，数组长度为arr1中最大元素加一，用于记录arr1中每个元素的出现次数。然后按照arr2的顺序，从频率数组中读取并构建结果数组，最后将剩余的未在arr2中出现的元素按照自然数顺序追加到结果数组的末尾。

时间复杂度: O(n + m + max)

空间复杂度: O(max)

# Definition for the solution class

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # 计数排序的频率数组，长度为arr1中的最大值加1
        frequency = [0] * (max(arr1) + 1)
        # 结果数组
        ans = []

        # 填充频率数组
        for item in arr1:
            frequency[item] += 1

        # 按arr2的顺序处理每个元素
        for num in arr2:
            if frequency[num] != 0:
                # 将arr2中的元素按其出现次数加入结果数组
                ans.extend([num] * frequency[num])
                # 处理完后设置频率为0，避免重复添加
                frequency[num] = 0

        # 添加未在arr2中出现的元素，按自然顺序排序
        for i, item in enumerate(frequency):
            if item != 0:
                ans.extend([i] * item)

        return ans

Explore

算法的输出不会受到arr1中元素出现顺序的影响。算法设计的核心是根据arr2的顺序来确定元素在输出数组中的排序，因此只要arr2的顺序固定，无论arr1中的元素如何排列，其在结果数组中的相对顺序都将按arr2中的顺序来排列。计数排序部分只是记录了arr1中每个元素的出现次数，而arr2决定了这些元素输出时的顺序。

选择`arr1中最大元素加一`作为频率数组的长度是因为这种方式可以直接利用元素的值作为数组索引，从而快速访问和更新元素的计数。这种方法简化了计数的过程，因为不需要额外的数据结构来映射元素到索引。如果基于实际的元素种类数来定义数组长度，则需要额外的映射机制来处理元素值和索引之间的关系，这可能会增加实现的复杂性并可能降低运行效率。

在当前算法框架下，将频率设置为0来`避免重复添加`是一种简单而有效的方法，因为它直接在遍历arr2时修改频率数组，避免了后续重复处理已经添加到结果数组的元素。这种方法的效率已经很高，因为它仅涉及基本的数组操作。尽管存在其他方法，如使用额外的集合或映射来跟踪已处理的元素，但这些方法会增加额外的空间复杂度和可能的运行时间开销，因此，在大多数情况下，当前的方法提供了一个良好的效率和实现简易性的平衡。