164. Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

S1： sort and compare (O(nlogn))

S2: bucket sort(O(n))

n个数组成的数组有n-1个gap, 若n个数平均分布，最小gap为(max-min)/(n-1)

将gap作为桶宽度，对数组进行bucket sort，最终max gap一定在两桶之间

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        int minNum = nums[0];
        int maxNum = nums[0];
        for (int i : nums) {
            minNum = min(minNum, i);
            maxNum = max(maxNum, i);
        }
        int gap = max(1, (maxNum - minNum) / (n - 1));  //gap小于1时也要取1
        int length = (maxNum - minNum) / gap + 1;  //桶至少有两个
        vector<Bucket> buckets(length);
        for (int i : nums) {
            int idx = (i - minNum) / gap;
            buckets[idx].used = true;
            buckets[idx].min = min(buckets[idx].min, i);
            buckets[idx].max = max(buckets[idx].max, i);
        }
        int preMax = minNum;
        int maxGap = 0;
        for (const auto& i : buckets) {
            if (i.used) {
                int curGap = i.min - preMax;
                maxGap = max(maxGap, curGap);
                preMax = i.max;
            }
        }
        return maxGap;
    }

private:
    struct Bucket {
        int used;
        int min;
        int max;
        Bucket(): used(false), min(INT_MAX), max(INT_MIN) {}
    };
};

451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

S1: bucket sort O(n)

s长度为n，最多只有1 - n共n种frequency，可用桶排序

    string frequencySort(string s) {
        string result = "";
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        vector<string> bucket(s.size(), "");
        for (auto i : freq) {
            for (int k = i.second; k > 0; --k) {
                bucket[i.second - 1] += i.first;
            }
        }

        for (int i = s.size() - 1; i >= 0; --i) {
            if (!bucket[i].empty()) {
                result += bucket[i];
            }
        }
        return result;
    }

S2: sort O(nlogn)

根据frequency排序

    string frequencySort(string s) {
        string result = s;
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        vector<pair<int, char>> count(freq.size());
        int idx = 0;
        for (auto i : freq) {
            count[idx++] = make_pair(i.second, i.first);
        }
        idx = s.size() - 1;
        sort(count.begin(), count.end());
        for (auto p : count) {
            while (p.first > 0) {
                result[idx--] = p.second;
                p.first--;
            }
        }
        return result;
    }