12ms Radix-Sort (O(n), 256-based) and Counting-Sort (O(n)) Solution for C++


  • 0
    U

    Here I will use the radix sort, whose time complexity is O(digits * (n + BASE)) = O(4(n + 256)) = O(n), and space complexity is O(n + BASE) = O(n + 256) = O(n).

    I treat all numbers as 256-based (rather than traditional 10-based), so we could get rid of the time-consuming "/" and "%" operators, and use the efficient bit-wise operators like ">>" and "&" instead.

    For a 32-bit non-negative integer, it contains at most 4 digits (256-based), as illustrated below:

    INT_MAX = 0x 7F[digit 3] FF[digit 2] FF[digit 1] FF[dgit 0] (256-based)

    class Solution {
    private:
        const int BASE = 256;
        const int INT_BASESIZE = sizeof(int) * BASE;
        int n = 0;
        int *numCounts = nullptr;
        int *keys = nullptr;
        
        inline void countingSort(vector<int> &source, vector<int> &target, int digitIndex) {
            memset(numCounts, 0, INT_BASESIZE);
            for (int i = 0; i < n; i++) {
                keys[i] = (source[i] >> digitIndex) & 0xFF;
                numCounts[keys[i]]++;
            }
            for (int i = 1; i < BASE; i++)
                numCounts[i] += numCounts[i - 1];
            for (int i = n - 1; i >= 0; i--)
                target[--numCounts[keys[i]]] = source[i];
        }
        
    public:
        int maximumGap(vector<int> &num) {
            n = num.size();
            if (n < 2) return 0;
            numCounts = new int[BASE];
            keys = new int[n];
            
            vector<int> num2(n);
            countingSort(num, num2, 0);
            countingSort(num2, num, 8);
            countingSort(num, num2, 16);
            countingSort(num2, num, 24);
            
            int maxGap = 0;
            for (int i = 1; i < n; i++) {
                int gap = num[i] - num[i - 1];
                if (gap > maxGap)
                    maxGap = gap;
            }
            return maxGap;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.