從LeetCode學演算法 - 86 Hash Table (7)

1331. Rank Transform of an Array (Easy)

Question

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1

1
2
3
Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2

1
2
3
Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3

1
2
Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints

0 <= arr.length <= 10^9
-10^9 <= arr[i] <= 10^9

分析/解題

給定一個陣列，將其依照大小順序排出rank。
(由1開始，大小相同則相同rank，數字越大，其rank則越大)

由於我們需要按照大小相同來排定rank，所以顯然我們需要將其排序後，
才能知道誰應該在第幾個。對於這樣子的題目，
一般而言我們不需要自己實作排序的過程，除非面試官要求，
否則說明清楚你使用了排序即可；
不要忘記對於沒有特別安排的資料結構，
一般程式語言所使用的排序法基本上都是O(N log N) 的時間複雜度，
所以最後在問複雜度時記得納入考量。

既然我們需要取代原先的陣列，所以我們必須另外增加一組記憶體空間，
用來存放排序的狀態。存放好以後，應該要怎麼去記錄呢？
由於相同的數字要擁有相同的rank，對於存取和讀出擁有最快的複雜度的，
就是Hash Table了！我們可以先檢查當下該數字是否已經放入對應 ，
若還沒有放入對應，則需要寫入(number, rank)的對應。
這時候rank是多少呢？應該要將已經置入的配對數量+1 來計算。
(因為代表現在已經給到多少數量的rank了)
都放完以後，再依序將陣列中的每個值作為key，
來從Hash Table得到其對應的rank(value)，再覆蓋掉即可。

依此，寫成程式碼：

Java

Java在增加新的記憶體儲存一份陣列時，可以使用Arrays.copyOf() 。
(後面加length可以指定複製的總長度)
使用HashMap來進行存放，並且用putIfAbsent(key, value) ，
僅在不存在對應時才進行寫入。
最後再利用HashMap.get()來一一取得對應rank並寫入。

Python

Python的部分，我們可以直接使用sorted(arr)取得一份新的串列。
也可以使用list.copy() 或者arr[:] 的方式來取得複製的串列。
請注意 “sArr = arr” 和 “sArr = arr[:]“意義上是不同的，
後者才是完整複製一份arr的串列 ，前者是新增了一個變數名稱，
但其記憶體位址依舊是指向到arr的！(也就是後者並沒有進行複製)

Java中使用HashMap，在Python中則用Dictionary達到，
而對應到putIfAbsent的函式則是setdefault 。
(也可以用if ** a not in rk: rk[a] = len(rk) + 1**)

最後，使用map函式來一一得到arr對應到rk.get的內容。
(即每次從arr依序取出元素再代入到rk.get內)

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(NlogN)/O(N))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**