原文链接: https://leetcode-cn.com/problems/relative-sort-array

英文原文

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

 

Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

Example 2:

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]

 

Constraints:

• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• All the elements of arr2 are distinct.
• Each arr2[i] is in arr1.

中文题目

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

通过代码

高赞题解

分析：

• 最近一直在做数组的题目，这种题一眼就想到了计数排序，唯一的不同就是在排序的时候要按 arr2 的顺序排。
• 我的代码是遍历了两边，第一遍是遍历 arr2，第二遍遍历整个排序，如果你有更好的计数排序方法，欢迎你告诉我。
• 不知道你们有没有遇到过计数排序，我尽可能的把注释写的详细一点，好给没接触过的人参考一下。（反正多遇到几次就写的很熟了）
• 其实就是用到了 hash 表。

代码：

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        arr = [0 for _ in range(1001)]  # 由于题目说 arr1 的范围在 0-1000，所以生成一个 1001 大小的数组用来存放每个数出现的次数。
        ans = []  # 储存答案的数组。
        for i in range(len(arr1)):  # 遍历 arr1，把整个arr1的数的出现次数储存在 arr 上，arr 的下标对应 arr1 的值，arr 的值对应 arr1 中值出现的次数。
            arr[arr1[i]] += 1  # 如果遇到了这个数，就把和它值一样的下标位置上 +1，表示这个数在这个下标 i 上出现了 1 次。
        for i in range(len(arr2)):  # 遍历 arr2，现在开始要输出答案了。
            while arr[arr2[i]] > 0:  # 如果 arr2 的值在 arr 所对应的下标位置出现次数大于 0，那么就说明 arr 中的这个位置存在值。
                ans.append(arr2[i])  # 如果存在值，那就把它加到 ans 中，因为要按 arr2 的顺序排序。
                arr[arr2[i]] -= 1  # 加进去了次数 -1 ，不然就死循环了。
        for i in range(len(arr)):  # 如果 arr1 的值不在 arr2 中，那么不能就这么结束了，因为题目说了如果不在，剩下的值按照升序排序。
            while arr[i] > 0:  # 同样也是找到大于 0 的下标，然后一直加到 ans 中，直到次数为 0。
                ans.append(i)
                arr[i] -= 1
        return ans  # 返回最终答案。

复杂度分析：

• 时间复杂度：O(n+m) n 为 arr2 的长度，m 为 arr1 的长度。arr 的长度固定是 1001，所以就算 arr 中只有 1 个有次数,也要遍历 1001 遍。
• 空间复杂度：O(n) n 为 arr1 的长度。

统计信息

通过次数	提交次数	AC比率
66887	94625	70.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言