🔗 🟢 1331. Rank Transform of an Array 1356

tags: Biweekly Contest 18 陣列(Array) 雜湊表(Hash Table) 排序(Sorting)

題意

給定一個整數陣列 arrarr，將每個元素替換為其排序後的排名。

排名代表元素的大小。排名編號的規則如下：

  • 排名從 11 開始。
  • 元素越大，排名越大。如果兩個元素相等，它們的排名必須相同。
  • 排名應該盡可能小。

思路：使用集合去重後排序，使用雜湊表記錄排名

首先，由於相同的元素排名必須相同，因此我們可以使用 集合(Set) 來去除重複的元素。

接著，我們將集合中的元素由小到大進行 排序(Sorting) ，其中最小的元素對應排名 11，次小的元素對應排名 22，以此類推。使用 雜湊表(Hash Table) 來記錄每個元素的排名。

最後，我們遍歷原陣列，並使用雜湊表來查找每個元素的排名，得到結果陣列 ansans。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，其中 nn 是陣列 arrarr 的長度。
    • 主要時間消耗在於對去重後的元素進行排序，這需要 O(nlog⁡n)\mathcal{O}(n \log n) 的時間。
    • 遍歷排序後的集合和查詢排名的操作都是線性時間 O(n)\mathcal{O}(n)。
  • 空間複雜度：O(n)\mathcal{O}(n)
    • 需要額外的空間來存儲去重後的集合和記錄排名的雜湊表，在最壞情況下(所有元素都不相同)，這些數據結構的大小與輸入陣列的大小相當。
    • 排序的空間複雜度為 O(n)\mathcal{O}(n) 或 O(log⁡n)\mathcal{O}(\log n)，取決於排序演算法。
1
2
3
4
5
6
class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        rank = dict()
        for i, k in enumerate(sorted(set(arr)), 1):
            rank[k] = i
        return [rank[x] for x in arr]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        int n = arr.size();
        set<int> s(arr.begin(), arr.end());
        unordered_map<int, int> rank;
        int i = 1;
        for (auto x : s) rank[x] = i++;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) ans[i] = rank[arr[i]];
        return ans;
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), long hair, (black eyes), looking at viewer, (standing), full body, black hair, school uniform, short sleeves, pleated skirt, skirt, shirt, (green top, green shirt), black bottom, (black skirt), serafuku, socks, looking back, indoors, sailor collar, black footwear, window, white socks, hallway,

A girl in a green shirt and black pleated skirt standing, in a long school hallway, windows and doors on both sides, bright natural light coming through the windows, serene atmosphere, looking back at the camera,