C++ solution, using bucket to record!


  • 5
    L
    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);
        vector<int> max_b(size_num, INT_MIN), min_b(size_num, INT_MAX);
        for (int i = 0; i < size_num; i++) {
            int index = (nums[i] - minV) / range;
            max_b[index] = max(max_b[index], nums[i]);
            min_b[index] = min(min_b[index], nums[i]);
        }
        int max_g = (int)range,  start = max_b[0];
        for (int i = 1; i < size_num; i++) {
            if (min_b[i] == INT_MAX) continue;
            max_g = max(max_g, min_b[i] - start);
            start = max_b[i];
        }
        return max_g;
    }

  • 0

    Dear, why can not I use the float instead of the double.

    when I use the float I find the case [2, 9999999] is wrong . I don' t understand why 9999999-2 will result

    1e+8, can you explain to me ???

    class Solution {
        public:
            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;
                float range=(maxV-minV)/float(size_num-1);
                cout<<"range:"<<maxV<<"-"<<minV<<"="<<(int)(maxV-minV/float(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;
            }
        };

  • 0
    Y

    it's counting sort. it's bucket sort. but it's not using radix sort at all.


  • 0
    M
    This post is deleted!

  • 0
    L

    Yes, you are right, I meant to write count, but radix just come here without thinking! My mistake!


  • 0
    L

    using float, it will over-flow.


  • 0
    S

    With float, you have only about 7 significant digits. 9999999 is really close to or possibly already past the limit of single precision. You may want to switch to double instead.


Log in to reply
 

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