Python 中的相对排序数组

pythonserver side programmingprogramming更新于 2026/1/4 18:52:17

假设我们有两个数组 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]

为了解决这个问题，我们将遵循以下步骤 −

创建一个名为 D 的映射，并存储 arr1 中存在的元素的频率
定义两个数组 res 和 temp
对于 arr2 中的每个元素 i −
- 对于 j 在 0 到 D[i] 范围内 – 1
  - 将 i 附加到 res 中
- D[i] := 0
对于 D 中的 (key, value) 对
- 如果 value 不为 0，则
  - 对于 i := 0 到 value – 1
    - 将 key 添加到 temp 中
对 temp 数组进行排序，将 temp 添加到 res 末尾，然后返回 res

示例

让我们看看下面的实现以便更好地理解 −

class Solution(object):
   def relativeSortArray(self, arr1, arr2):
      d = {}
      for i in arr1:
         if i not in d:
            d[i]= 1
         else:
            d[i]+=1
      res = []
      temp = []
      for i in arr2:
         for j in range(d[i]):
            res.append(i)
         d[i] =0
      for k,v in d.items():
         if v:
            for i in range(v):
               temp.append(k)
      temp.sort()
      res.extend(temp)
      return res
ob1 = Solution()
print(ob1.relativeSortArray([2,3,1,4,2,4,6,7,9,2,19] ,[2,1,4,3,9,6]))