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
不過第二種方法也沒比較快就是了
而且不用對原列表修改 其實直接做一個新列表比較快 姆咪