[recommend for beginners] 2 different clean C++ implementations with detailed explaination


  • 2

    As far as I am concerned, I think you should grasp the 3 linear-time-sorting-algorithm-implementation introduced at
    https://leetcode.com/discuss/80529/recommend-beginners-implementation-detailed-explaination

    Then you can quickly understand the following 2 implementation. They are just the small changed version of the original implementation.

    class Solution {
    public:
        /* bucket-sort-inspired-ideas-implementation */
        int maximumGap(vector<int>& nums) {
            const int size_num=nums.size();
            if(size_num < 2)    return 0;
            int maxV=*max_element(nums.begin(), nums.end());
            int minV=*min_element(nums.begin(), nums.end());
            if(maxV==minV)  return 0;
            double range=(maxV-minV)/double(size_num-1);
            cout<<"range:"<<maxV<<"-"<<minV<<"="<<(int)(maxV-minV/double(1))<<endl;
            vector<int> max_bucket(size_num, INT_MIN);
            vector<int> min_bucket(size_num, INT_MAX);
            for(int i=0; i<size_num; i++){
                int index=(nums[i]-minV)/range;
                max_bucket[index]=max(max_bucket[index], nums[i]);
                min_bucket[index]=min(min_bucket[index], nums[i]);
            }
            
            int max_gap=(int)range, start=max_bucket[0];
            cout<<max_gap<<endl;
            for(int i=1; i<size_num; i++){
                if(min_bucket[i]==INT_MAX) continue;
                max_gap = max(max_gap, min_bucket[i]-start);
                start=max_bucket[i];
            }
            return max_gap;
        }
        
        /* radix-based-sorting-implementation */
        int maximumGap(vector<int>& nums){
        	if (nums.size() < 2)	return 0;
        	int max_val = *max_element(nums.begin(), nums.end());
        	int exp = 1;
        	int R = 10;
        	vector<int> aux(nums.size(), 0);
        
        	while (max_val / exp > 0){
        		vector<int> count(R, 0);
        		for (int i = 0; i < nums.size(); i++){
        			count[(nums[i] / exp) % 10]++;
        		}
        		for (int i = 1; i < count.size(); i++){
        			count[i] += count[i - 1];
        		}
        		for (int i = nums.size() - 1; i >= 0; i--){
        			aux[--count[(nums[i] / exp) % 10]] = nums[i];
        		}
        
        		for (int i = 0; i < nums.size(); i++){
        			nums[i] = aux[i];
        		}
        		exp *= 10;
        	}
        
        	int result = 0;
        	for (int i = 1; i < aux.size(); i++){
        		result = max(result, aux[i] - aux[i - 1]);
        	}
        
        	return result;
        }
    };
    

  • 1

    Here is the 3-method-implementation-AC-code.

    I should notice one possible bug.

          int index=len*(nums[i]-min_val)/(double)range;
    

    This code have the potential to be OVER_FLOW !

    Why because the big integer multiply big integer can cause overflow if you do not change the type.

    So the right way should be like this:

         int index=len* ((nums[i]-min_val)/(double)range);
    

    Code:

    class Solution {
    public:
    int maximumGap(vector<int>& nums) {
    int n=nums.size();
    if(n<=1) return 0;
    //countingSort(nums, 1, INT_MAX);
    //radixSort(nums);
    bucketSort(nums);
    int result=0;
    for(int i=1; i<n; i++){
    result=max(result, nums[i]-nums[i-1]);
    }
    return result;
    }

        /** method 1 : only-counting-sort **/
        void countingSort(vector<int>& nums){
            int len=nums.size();
            int range=0;
            int start=INT_MAX, end=INT_MIN;
            for(int i=0; i<len; i++) { start=min(start, nums[i]);  end=max(end, nums[i]); }
            range=end-start+1;
            vector<int> count(range,0);
            vector<int> result(len,0);
            for(int i=0; i<len; i++) count[nums[i]-start]++;
            /** loop the [0,range-1] **/
            for(int i=1; i<range; i++) count[i]+=count[i-1];
            for(int i=len-1; i>=0; i--){
                result[count[nums[i]-start]-1]=nums[i];
                count[nums[i]-start]--;
            }
            /** re-assign the result-vector to the original-vector **/
            for(int i=0; i<len; i++)  nums[i]=result[i];
            return;
        }
        
        /** method2 : radix-sort **/
        void countingSort(vector<int>& nums, int exp, int base){
            #define A(a) ((a/exp)%base)
            int n=nums.size();
            int start=INT_MAX, end=INT_MIN;
            int range=0;
            for(int i=0; i<n; i++) { start=min(start, A(nums[i]));  end=max(end, A(nums[i])); }
            range=end-start+1;
            vector<int> count(range);
            vector<int> result(n);
            for(int i=0; i<n; i++) { count[A(nums[i])-start]++; }
            for(int i=1; i<range; i++) { count[i]+=count[i-1]; }
            for(int i=n-1; i>=0; i--){
                result[count[A(nums[i])-start]-1]=nums[i];
                count[A(nums[i])-start]--;
            }
            for(int i=0; i<n; i++)  nums[i]=result[i];
        }
        void radixSort(vector<int> &nums){
            int len=nums.size();
            int max_val=INT_MIN;
            int base=10;
            for(int i=0; i<len; i++)  max_val=max(max_val, nums[i]);
            for(int exp=1; max_val/exp>0; exp*=base){
                countingSort(nums, exp, 10);
            }
        }
        
        /** method3 : bucket-sort **/
        void bucketSort(vector<int>& nums){
            int len=nums.size();
            int max_val=nums[0], min_val=nums[0];
            for(int i=1; i<len; i++) { 
                max_val=max(max_val, nums[i]);
                min_val=min(min_val, nums[i]);
            }
            int range=max_val-min_val;
            
            if(range==0)  return;
            vector<vector<int>> bucket(len+1, vector<int>());
        
            for(int i=0; i<len; i++){
                int index=len*((nums[i]-min_val)/(double)range);
                bucket[index].push_back(nums[i]);
            }
            for(int i=0; i<=len; i++) {
                if(bucket[i].size()>0)  sort(bucket[i].begin(), bucket[i].end());
            }
            int index=0;
            for(int i=0; i<=len; i++){
                for(int j=0; j<bucket[i].size(); j++){
                    nums[index++]=bucket[i][j];
                }
            }
        }
    };

  • 0

    The important intuition is that to infer the gap to be (max-min)/(n-1), then the max_gap must is bigger than that, so we set the intra distance in a bucket is (max-min)/(n-1)


Log in to reply
 

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