easy radix sort C++


  • 0
    V

    Algorithm does radix sort for numbers by their binary representation.

    mask - helps to check if i-th digit is set to 1.
    cnt1 - count numbers with i-th bit set to 1.

    int maximumGap(vector<int>& nums) {
            if (nums.size() < 2) return 0;
            int n = nums.size();
            for(int i = 0; i < 32; ++i)
            {
                int mask = 1LL << i;
    
                int cnt1 = 0;
                for (int j = 0; j < n; ++j) if (mask & nums[j]) ++cnt1;
                
                vector<int> newn(n);
                int k0 = 0;
                int k1 = 0;
                for (int j = 0; j < n; ++j)
                {
                    if (nums[j] & mask) newn[(n-cnt1) + k1++] = nums[j];
                    else newn[k0++] = nums[j];
                }
                swap(newn, nums);
            }
            int mx = 0;
            for (int i = 1; i < n; ++i)
            {
                mx = max(mx, nums[i] - nums[i-1]);
            }
            return mx;
        }
    

Log in to reply
 

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