# Leetcode刷題學習筆記-- Counting Sort, Radix Sort
## Counting Sort
### Reference
ref1 : [Counting Sort from GeeksforGeeks](https://www.geeksforgeeks.org/counting-sort/)
ref2 : [Counting Sort from Leetcode](https://leetcode.com/explore/learn/card/sorting/695/non-comparison-based-sorts/4437/)
### Introduction
當需要排序的數列範圍不是很大的時候，可以使用counting sort。
+ non comparison-based algorithm
+ non In Place algorithm
### Procedure
1. 宣告一個vector來記錄所以數值可能出現的範圍。
```cpp
vector<int> nums{5, 3, -1, 2, 4};
auto [mn, mx] = minmax_element(begin(nums), end(nums));
int range = *mx - *mn + 1, shift = *mn;
vector<int> count(range);
```
2. 統計每個數字出現的次數
``` cpp
for(auto& n : nums)
count[n - shift]++;
```
3. 計算prefix sum得到每個數字要排序的位置。
```cpp
for(int i = 1; i < count.size(); ++i)
count[i] += count[i - 1];
```
或是使用
```cpp
partial_sum(count.begin(), count.end(), count.begin());
```
4. 使用一個和nums一樣大的vector來記錄排序後的結果，從後面走訪來保持stable。
```cpp
vector<int> result(nums.size());
for(int i = nums.size() - 1; i >= 0; --i) {
result[count[nums[i] - shift] - 1] = nums[i];
count[nums[i] - shift]--;
}
```
5. 把結果回傳回去，或是覆蓋原本的輸入vector。
```cpp
nums = result; // 會呼叫vector的copy assignment。
```
### Example
#### [75. Sort Colors](https://leetcode.com/problems/sort-colors/)
```cpp
void sortColors(vector<int>& nums) {
vector<int> count(3), tmp(nums.size());
for(auto& n : nums) count[n]++;
partial_sum(count.begin(), count.end(), count.begin());
for(int i = nums.size() - 1; i >= 0; --i) {
tmp[count[nums[i]] - 1] = nums[i];
count[nums[i]]--;
}
nums = tmp;
}
```
#### [1200. Minimum Absolute Difference](https://leetcode.com/problems/minimum-absolute-difference/)
```cpp
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
const auto [mn, mx] = minmax_element(begin(arr), end(arr));
int range = *mx - *mn + 1, shift = *mn;
vector<int> count(range);
for(auto& n : arr) count[n - shift]++;
int left = 0, right = left + 1, mindiff = INT_MAX;
vector<vector<int>> ans;
while(right < count.size()) {
right = left + 1;
while(right < count.size() && count[right] == 0) ++right;
if(right < count.size()) {
int diff = right - left;
if(diff < mindiff) {
mindiff = diff;
ans = {{left + shift, right + shift}};
} else if(diff == mindiff)
ans.push_back({left + shift, right + shift});
left = right;
} else
break;
}
return ans;
}
```
## Radix Sort
### Reference
ref : [Radix Sort from GeeksforGeeks](https://www.geeksforgeeks.org/radix-sort/)
ref : [Radix Sort from Leetcode](https://leetcode.com/explore/learn/card/sorting/695/non-comparison-based-sorts/4438/)
### Introduction
+ 所有的comparsion based sorting algorithm 最快就是$O(NlogN)$
+ 可以達到線性的time complxity只有counting sort和radix sort。
+ 但是counting sort對數字範圍很大的比較不利。
+ 從least significant digit一直排序到most significant digit
+ non in-place algorithm
+ Stable Sort
### Procedure
1. 先取得最大值或是最長的字串，因為這是要做多少次counting sort的基礎。
如果使用max_element得到的為iterator，必須在使用前先取值，不然數值會被第一次排序後改變。
```cpp
vector<int> nums;
int maxv = *max_element(begin(nums), end(nums));
```
2. 對每個位數做counting sort
exp = 1, 10, 100, 1000, ...
```cpp
for(int exp = 1; maxv / exp > 0; exp *= 10) {
countSort(nums, exp);
}
```
3. 對某個位數進行counting sort
```cpp
void countSort(vector<int>& nums, int exp) {
vector<int> output(nums.size());
vector<int> count(10); // 因為數字為0~9
for(auto& n : nums) // 統計每個數字的個數
count[(n / exp) % 10]++;
// 計算每個數字的開頭index
partial_sum(begin(count), end(count), begin(count));
// 產生根據這個exp的排序
for(int i = nums.size() - 1; i >= 0; --i) {
output[count[(nums[i] / exp) % 10] - 1] = nums[i];
count[(nums[i] / exp) % 10]--;
}
// 取代原先的input vector
nums = output;
}
```
### Complexity
#### Time Complexity
==$O(W(N+K))$==
其中$O(N+K)$ 為counting sort，
N: 要被排序vector的大小
K: size of counting vector
W: 最大數值的位數。$W = log10(MaxValue)$
#### Space complexity
和counting sort一樣
$O(N+K)$
### Problems
#### [2343. Query Kth Smallest Trimmed Number](https://leetcode.com/problems/query-kth-smallest-trimmed-number/)
```cpp
class Solution {
void countSort(vector<string>& nums, int pos, vector<int>& idx) {
vector<int> oidx(idx.size());
vector<int> count(10);
for(auto& n : nums)
count[n[pos] - '0']++;
partial_sum(begin(count), end(count), begin(count));
for(int i = nums.size() - 1; i >= 0; --i) {
string str = nums[idx[i]];
char c = str[pos];
int j = c - '0';
oidx[count[j] - 1] = idx[i];
count[j]--;
}
idx = oidx;
}
public:
vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
unordered_map<int, vector<int>> m;
vector<int> idx(nums.size());
iota(idx.begin(), idx.end(), 0);
int sz = nums[0].size();
for(int i = 1; i <= sz; ++i) {
countSort(nums, sz - i, idx);
m[i] = idx;
}
vector<int> rtn;
for(auto& q : queries)
rtn.push_back(m[q[1]][q[0] - 1]);
return rtn;
}
};
```
#### [164. Maximum Gap](https://leetcode.com/problems/maximum-gap/)
```cpp
class Solution {
void countSort(vector<int>& nums, int exp) {
vector<int> output(nums.size());
vector<int> count(10);
for(auto& n : nums) count[(n / exp) % 10]++;
partial_sum(count.begin(), count.end(), count.begin());
for(int i = nums.size() - 1; i >= 0; --i) {
int n = (nums[i] / exp) % 10;
output[count[n] - 1] = nums[i];
count[n]--;
}
for(int i = 0; i < nums.size(); ++i)
nums[i] = output[i];
}
public:
int maximumGap(vector<int>& nums) {
int maxval = *max_element(nums.begin(), nums.end());
for(int exp = 1; maxval / exp > 0; exp *= 10)
countSort(nums, exp);
int ans = 0;
for(int i = 1; i < nums.size(); ++i)
ans = max(ans, nums[i] - nums[i - 1]);
return ans;
}
};
```
###### tags: `leetcode` `刷題`
Sign in with Wallet
Connect another wallet