数组的相对排序

难度: Easy

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

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

示例 1：

输入：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]

示例 2:

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

提示：

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中

Submission

运行时间: 23 ms

内存: 16.2 MB

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        upper = max(arr1)
        countarr = [0] * (upper + 1)
        for i in arr1:
            countarr[i] += 1
        res = []
        for j in arr2:
            res.extend([j]*countarr[j])
            countarr[j] = 0
        for j in range(0, max(arr1)+1):
            if countarr[j]>0:
                res.extend([j]*countarr[j])
        return res

Explain

该题解采用计数排序的思路来实现。首先，通过一个数组`countarr`来统计`arr1`中每个元素的出现次数。然后，根据`arr2`的顺序，将`arr1`中相应的元素按`arr2`的顺序添加到结果列表`res`中，并在`countarr`中相应减少计数。最后，对于`arr1`中存在但不在`arr2`中的元素，按照升序添加到`res`的末尾。

时间复杂度: O(n + u)

空间复杂度: O(u + n)

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        upper = max(arr1) # 找到arr1中的最大值
        countarr = [0] * (upper + 1) # 创建计数数组
        for i in arr1: # 统计arr1中每个元素的出现次数
            countarr[i] += 1
        res = [] # 初始化结果列表
        for j in arr2: # 按arr2的顺序添加到结果列表
            res.extend([j]*countarr[j])
            countarr[j] = 0 # 处理完的元素计数清零
        for j in range(0, upper+1): # 添加未在arr2中出现的元素
            if countarr[j] > 0:
                res.extend([j]*countarr[j])
        return res

Explore

计数排序特别适合于当输入的元素是有确定范围的整数时。在本题中，由于`arr1`的元素范围可以通过`arr2`和`arr1`最大值确定，使用计数排序可以达到线性时间复杂度O(n)，这比常规的比较排序算法（如快速排序、归并排序等）的O(n log n)更高效。此外，计数排序可以直接根据`arr2`的顺序处理`arr1`中的元素，使其按照特定的顺序输出，这正是此题的需求。

在实现中，算法会初始化一个足够大的计数数组`countarr`来覆盖`arr1`中可能出现的所有元素。当按照`arr2`的顺序遍历并添加元素到结果列表`res`时，如果某个元素在`arr1`中不存在，那么在`countarr`中该元素对应的计数将为0。所以，尽管这个元素出现在`arr2`中，它不会被添加到`res`中，因为没有相应的元素来添加（计数为0）。

虽然某些数字在`arr1`中可能从未出现过，但计数排序的一个重要步骤是能够处理并包含所有可能的值，以确保排序的完整性和正确性。遍历从0到`upper+1`确保了所有可能的元素都被考虑进去，这对于在最终结果中正确地添加那些实际出现在`arr1`中但未在`arr2`中指定顺序的元素是必需的。这样做也保证了算法的稳定性和预期的输出顺序。

在将`arr2`中的元素添加到结果列表`res`时，将对应在`countarr`中的计数置为0的目的是为了防止这些元素被重复添加。因为在后续步骤中，我们还需要处理那些存在于`arr1`中但不在`arr2`中的元素。如果不将计数置为0，那么这些已经在结果中按`arr2`顺序添加过的元素可能会再次被添加，从而导致结果错误。这也是确保算法正确性的一种方式。