1122. 数组的相对排序

1122. 数组的相对排序 #

  • 标签:数组、哈希表、计数排序、排序
  • 难度:简单

题目大意 #

给定两个数组,arr1arr2,其中 arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1 中。

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

注意:

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000

解题思路 #

因为元素值范围在 [0, 1000],所以可以使用计数排序的思路来解题。

使用数组 count 统计 arr1 各个元素个数。

遍历 arr2 数组,将对应元素num2 按照个数 count[num2] 添加到答案数组 ans 中,同时在 count 数组中减去对应个数。

然后在处理 count 中剩余元素,将 count 中大于 0 的元素下标依次添加到答案数组 ans 中。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count = [0 for _ in range(1010)]
        for num1 in arr1:
            count[num1] += 1
        res = []
        for num2 in arr2:
            while count[num2] > 0:
                res.append(num2)
                count[num2] -= 1

        for num in range(len(count)):
            while count[num] > 0:
                res.append(num)
                count[num] -= 1

        return res
本站总访问量  次  |  您是本站第  位访问者