前往
大廳
主題

LeetCode - 1122. Relative Sort Array 解題心得

Not In My Back Yard | 2021-03-26 00:00:05 | 巴幣 0 | 人氣 328

題目連結:


題目意譯:
給定兩陣列 arr1 和 arr2,arr2 的所有元素皆相異,且所有 arr2 的元素也在 arr1 中。

請排序 arr1 的元素,使得 arr1 的元素之相對順序跟 arr2 一致。沒有出現於 arr2 中的元素應由小到大放置於 arr1 的結尾。

限制:
1 ≦ arr1.length, arr2.length ≦ 1000
0 ≦ arr1[i] 、 arr2[i] ≦ 1000
arr2 的所有元素皆相異。
每個 arr2[i] 都在 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]


解題思維:
先掃過一次 arr1 的所有數字,並統計每個數字的出現次數。

接著再掃過 arr2 中的每個數字,對於每個數字 arr2[i],將根據 arr2[i] 在 arr1 中的出現次數(剛剛有統計)放置等量的 arr2[i] 於答案陣列中。

最後,再將剩下的數字由小到大(也是根據統計結果,由小的數字掃到大的)放入答案陣列之中。做完之後,答案陣列即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作