https://leetcode.com/problems/relative-sort-array
1122. Relative Sort Array
给定两数列arr1与arr2 arr2的元素不重复且皆存在于arr1
请依照arr2的顺序排列arr1的元素
假设有元素不在arr2 请递增排序
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.
思路:
记数排序 但不在arr2的元素要多付出一个sort排序
所以时间复杂度是nlogn
Python Code:
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) ->
List[int]:
record = defaultdict(int)
exception = []
for n in arr1:
if n in arr2:
record[n] += 1
else:
exception.append(n)
i = 0
for n in arr2:
c = record[n]
while c > 0:
arr1[i] = n
c -= 1
i += 1
exception.sort()
while exception:
x = exception.pop(0)
arr1[i] = x
i += 1
return arr1
思路二:
改用list纪录 因为元素最大就1000 所以开一个1001大小的list
最后从0开始由小到大遍历list 遇到不在arr2的元素就加进去arr1
这样就可以省下一个sort
时间复杂度是n
Python Code:
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) ->
List[int]:
record = [0] * 1001
for n in arr1:
record[n] += 1
i = 0
for n in arr2:
while record[n] > 0:
arr1[i] = n
record[n] -= 1
i += 1
for j in range(1001):
while record[j] > 0:
arr1[i] = j
record[j] -= 1
i += 1
return arr1
不过第二种方法也没比较快就是了
而且不用对原列表修改 其实直接做一个新列表比较快 姆咪