I directly sort the vector, and then get the max gap, it cost 52ms, std is powerful.


  • 2
    F

    At Beginning, I using the std::sort to make the vector in order, and then get the max gap, after submit it, it cost 52ms. Then I follow the solution provided by leetcode, and it cost 44ms, but it cost me almost 2 hours to finish it. It seems that sometimes I cost large time to get a solution which seems to be a good solution, and it may not reduce too much cost when comparing with some easy way.

    #include <iostream>
    #include <functional>
    
    // Solution 1 cost 52ms
    int solution_1(std::vector<int> &num)
    {
        if (num.size() < 2)
        {
            return 0;
        }
        
        std::sort(num.begin(), num.end());
        int gap = 0;
        
        for(int n = 0, m = 1; m < num.size(); ++n, ++m)
        {
            int tmp_gap = num[m] - num[n];
            if (tmp_gap > gap)
            {
                gap = tmp_gap;
            }
        }
        
        //std::cout << gap << "\n";
        
        return gap;
    }
    
    
    // Solution2 according to suggestion by leetcode
    // This solution cost 44ms
    
    typedef struct Bucket_S
    {
        int gap;
        int max;
        int min;
    } Bucket_T;
    
    void add2bluck(Bucket_T& bucket, int value)
    {
        if (bucket.max == -1)
        {
            bucket.max = value;
            bucket.min = value;
        }
        else
        {
            if (bucket.max < value)
            {
                bucket.max = value;
            }
            else if (bucket.min > value)
            {
                bucket.min = value;
            }
        }
    }
    
    int getIndexInBucket(int min, int value, int min_gap)
    {
        return (value - min)/min_gap;
    }
    
    void caculateGapSelf(Bucket_T& bucket)
    {
        if (bucket.max != -1)
        {
            bucket.gap = bucket.max - bucket.min;
        }
    }
    
    int solution_2(std::vector<int> &num)
    {
        if (num.size() < 2)
        {
            return 0;
        }
        
        int max = num[0];
        int min = num[0];
        
        for (unsigned int i = 1; i < num.size(); ++i)
        {
            if (num[i] > max)
            {
                max = num[i];
            }
            else if (num[i] < min)
            {
                min = num[i];
            }
        }
        
    //    std::cout << "Max: " << max <<" Min: "<< min << "\n";
        
        int min_gap = (max - min)/(num.size() - 1);
        if (min_gap == 0)
        {
            min_gap = 1;
        }
    //    std::cout << "Min Gap:"<<min_gap<<"\n";
        std::vector<Bucket_T> buckets;
        int total_buckets = (max - min)/min_gap + 1;
        for(unsigned int i = 0; i < total_buckets; ++i)
        {
            //std::cout<< i << "<<<";
            Bucket_T b;
            b.max = -1;
            b.min = -1;
            b.gap = -1;
            buckets.push_back(b);
    
        }
    
        int max_gap = 0;
        for (unsigned int i = 0; i < num.size(); ++i)
        {
            int index = getIndexInBucket(min, num[i], min_gap);
            //std::cout<< index << " " << num[i] << "\n";
            add2bluck(buckets[index], num[i]);
            caculateGapSelf(buckets[index]);
            if (buckets[index].gap > max_gap)
            {
                max_gap = buckets[index].gap;
            }
        }
    
        
        
        for(unsigned int n = 0, m = 0; ;)
        {
            while (buckets[n].max == -1)
            {
                ++n;
                if (n >= buckets.size()-1)
                {
                    return -1; // error condition
                }
            }
            m = n + 1;
            while (buckets[m].max == -1)
            {
                ++m;
                if (m > buckets.size()-1)
                {
                    return -1;
                }
            }
            int tmp_gap = buckets[m].min - buckets[n].max;
            if (tmp_gap > max_gap)
            {
                max_gap = tmp_gap;
            }
            ++n;
            if ( n >= buckets.size()-1 || m >= buckets.size() - 1)
            {
                break;
            }
        }
        
        return max_gap;
    }

  • 9
    P

    It is hard to tell the difference between O(N logN) solution and O(N) solution


  • 2
    R

    The time complexity of bucket sort is O(kn) where k is the number of digits of the largest element;

    Therefore, in order to make the bucket/radix sort more effective than the nlog(n) comparison sorting methods, we need kn < nlog(n) thus k< log(n).
    If the vector contains large element say INT_MAX(2^31-1) we need to deal with 10 digits, here k ==10. Then the length of vectors have to be at least 1024 to make the bucket sort more effective.

    Your two solutions gave similar time cost is probably because most of the test cases are short vectors.


  • 0
    W

    Thinking about an interviewer who is aiming at bucket sort solution, while you use std::sort, :)
    Just to make the 2 hours shorter, not to confused about the time cost between O(NlogN) / O(N)


  • 0
    H
    This post is deleted!

Log in to reply
 

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