image.png
重点
首先注意几个重点： 1. arr1和arr2里最大的元素不会超过1000 2. arr2里面没有重复的元素 3. arr2里面每个元素必定在arr1里面出现
思路
1. 先创建一个大小为1001的数组data用来存放arr1中每个元素出现的次数（因为最大值可能是1000），其实这里可以简化，只要这个数组的长度等于max(arr1)+1即可覆盖到所有arr1中的数字； 2. 创建一个大小为arr1的数组或者直接沿用arr1（因为arr1的信息已经被记录到data数组里面了） 3. 遍历arr2，去data中取出arr1中包含arr2元素的数量，分别插入这个新数组并把data里面arr2的相关数据都置为0，保证后续data中只有arr1中特有的元素。 4. 遍历data，把剩下的数据写到新数组。
方法一:
class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: # 创建一个能容纳arr1最大值的数组 data = [0] * (max(arr1)+1) # 存储arr1中的元素值和数量 for a in arr1: data[a] += 1 # 最终结果数组 result = [] # 把arr2的所有元素写入result数组 for d in arr2: length = data[d] for x in range(length): result.append(d) data[d] = 0 # i是data中剩余arr1数据的值，可能会有多个，所以需要插入n个i，当n等于0的时候代表n不存在或者n是arr2里的元素，直接continue for i, n in enumerate(data): if n == 0: continue for x in range(n): result.append(i) return result
优化(少用一个result数组，直接在arr1修改)
class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: data = [0] * (max(arr1)+1) for a in arr1: data[a] += 1 # 定义一个指针指向当前已经替换的元素 i = 0 for d in arr2: length = data[d] for x in range(i, i+length): arr1[x] = d i += length data[d] = 0 for j, n in enumerate(data): if n == 0: continue for x in range(i, i+n): arr1[x] = j i += n return arr1
image.png
