Leetcode刷題學習筆記 – Bucket Sort

Introduction

ref : Bucket Sort form GeeksforGeeks
ref : Bucket Sort from Leetcode
把目標數字分散在幾個桶子裡面，對每個桶子進行排序，最後依序取出數字，即為排序後的結果。

• 如果有負數的情況，可以分成兩個vector(正數和負數)，分別對兩個vector做bucket sort，最後再合併成一個。負數一定比較小，所以先取負數。
• ref : Bucket Sort To Sort an Array with Negative Numbers

使用情況

• 輸入是在一個範圍內，不規則的分佈。(input is uniformly distributed over a range)
• 針對非數值的範圍排序，例如:出現的頻率
  • 347. Top K Frequent Elements
• 如果範圍不大，可以降低sort的複雜度。
  • 對長度為N的vector進行排序，time complexity為
    $O(NlogN)$，但是使用bucket sort為O(N)

Procedure

1. 先找出最大最小值，計算shift和bucket間的range

vector<int>& nums;
auto [mn, mx] = minmax_element(begin(nums), end(nums));
int shift = *mn, range = (*mx - *mn) / k;

2. 建立k個bucket

vector<vector<int>> buckets(k, vector<int>());

3. 分配每個element進入bucket

for(auto& n : nums) {
    int idx = (n - shift) / range;
    buckets[idx].push_back(n);
}

4. 對每個bucket排序

for(auto& vec : buckets)
    sort(vec.begin(), vec.end());

5. 把所有的buckets內容收集到同一個vector

int idx = 0;
for(auto& vec : buckets) {
    for(auto& n : vec) {
        nums[idx++] = n;
    }
}

Time Complexity

worst case : 全部的數值都在同一個bucket，
等於沒分類的效果，就是看你的sort algoritm，最壞情況是

$O(N^2)$
best case : 每個bucket都只有一個element，不需要對每個bucket做sort，所以分配element:

$O(N)$，把bucket內容組合起來

$O(K)$，所以best case是

$O(N+K)$

	Best	Average	Worst
Bucket Sort	$O(N+K)$	$O(N+K)$	$O(N^2)$

Space complexity

需要額外的空間儲放所有的element，所以

$O(N)$

Example

220. Contains Duplicate III

給你一個vector<int> nums, 找出index差小於等於k，且數字差小於等於t。

$abs(num[i]-nums[j])<=t$ 且

$abs(i-j)<=k$。

1. 看到index差小於等於k，就會想到使用sliding window用兩個指標來代表window的前後。
2. 重點是window裡面的資料怎麼排列?
3. 因為兩個數的差小於等於t，可以使用bucket sort，每個bucket裡面的數字差一定小於等於t。
4. bucket裡面不會有兩個以上的數字，因為只要是兩個就會成立離開。
5. 還要跟前後的bucket去比較

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    int sz = nums.size();
    unordered_map<int, int> m;
    for(int i = 0, j = 0; i < sz; ++i) {
        // 計算bucket，因為t有可能為INT_MAX，所以轉成long
        int b = nums[i] / ((long)t + 1);
        // 因為負數也會有0的情況
        if(nums[i] < 0) b--;
        // 兩個數在同一個bucket，符合情況。
        if(m.count(b)) return true;
        // 檢查後一個bucket
        if(m.count(b + 1) && (long)m[b + 1] - nums[i] <= t) return true;
        // 檢查前一個bucket
        if(m.count(b - 1) && (long)nums[i] - m[b - 1] <= t) return true;
        // 把資料放入bucket
        m[b] = nums[i];
        // 移除超出範圍的數字
        if(i - j == k) {
            int bj = nums[j] / ((long)t + 1);
            if(nums[j] < 0) bj--;
            m.erase(bj);
            j++;
        }
    }
        
    return false;
}

347. Top K Frequent Elements

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq; // value, count
    for(auto& n : nums) freq[n]++;  // O(N)
        
    // create buckets, 因為最多出現次數為nums.size()
    vector<vector<int>> buckets(nums.size() + 1, vector<int>());
    for(auto& ref : freq)
        buckets[ref.second].push_back(ref.first); //O(N)
        
    vector<int> rtn; // O(K)
    for(int i = buckets.size() - 1; i >= 0; --i) {
        for(auto& n : buckets[i]) {
            rtn.push_back(n);
            k--;
            if(k == 0) return rtn;
        }
    }     
    // time  : O(N+N+K) = O(2N+K) = O(N+K)
    // space : O(N+N) = O(2N) = O(N)
    return {};
}

tags: leetcode 刷題