C++ solution with O(n) time and space


  • 0
    W
    class Solution {
    public:
        int maximumGap(vector<int> &num) {
            // 1、find max and min elemnet
            if (num.size()<2) return 0;
    		if (num.size()==2) return abs(num[0]-num[1]);
            int min_num = INT_MAX;
            int max_num = INT_MIN;
            int i;
            for (i=0; i<num.size(); i++) {
                if (num[i]<min_num)
                    min_num = num[i];
                if (num[i]>max_num)
                    max_num = num[i];
            }
            //2、create buckets, every bucket store min and max element if exit;
            int gap = (max_num-min_num)/(num.size()-1)+1;
            vector<vector<int> > temp(num.size());
            
            for(i=0; i<num.size(); i++) {
                int index = (num[i]-min_num)/gap;
                if (temp[index].empty()) 
                    temp[index].push_back(num[i]);
                else if (temp[index].size()==1) {
                    if (num[i]<temp[index][0]) {
                        temp[index].push_back(temp[index][0]);
                        temp[index][0] = num[i];
                    } else 
                        temp[index].push_back(num[i]);
                } else {
                    if (num[i]<temp[index][0])
                        temp[index][0] = num[i];
                    if (num[i]>temp[index][1])
                        temp[index][1] = num[i];
                }
            }
            //3、find max gap between bucket
            int ret=INT_MIN;
            vector<int> pre = temp[0];
            for (i=1; i<temp.size(); i++) {
                if (temp[i].empty())
                    continue;
                if (pre.size()==1) {
                    if (temp[i][0]-pre[0]>ret)
                        ret = temp[i][0]-pre[0];
                } else {
                    if (temp[i][0]-pre[1]>ret)
                        ret = temp[i][0]-pre[1];
                }
                pre = temp[i];
            }
            
            return ret;
        }
    };

  • 6
    J

    Your code won't save much space, so no need to make it a mess.

    Here is mine:

    class Solution {
    public:
        int maximumGap(vector<int> &num) {
            if (num.size() < 2) return 0;
            // find the minimum and the maximum
            int imax = num[0];
            int imin = num[0];
            for (int x : num) {
                if (x > imax) imax = x;
                if (x < imin) imin = x;
            }
            // each bucket has at most m numbers
            int m = (imax - imin) / num.size() + 1;
            // but we just need the minimum and the maximum of each bucket
            vector<vector<int>> buckets((imax - imin) / m + 1);
            for (int x : num) {
                int i = (x - imin) / m;
                if (buckets[i].empty()) {
                    buckets[i].reserve(2);
                    buckets[i].push_back(x);
                    buckets[i].push_back(x);
                } else {
                    if (x < buckets[i][0]) buckets[i][0] = x;
                    if (x > buckets[i][1]) buckets[i][1] = x;
                }
            }
            // calculate the maximal gap
            int gap = 0;
            int prev = 0;
            for (int i = 1; i < buckets.size(); i++) {
                if (buckets[i].empty()) continue;
                gap = max(gap, buckets[i][0] - buckets[prev][1]);
                prev = i;
            }
            return gap;
        }
    };

  • 0
    M

    An alternative: The vector of vectors you have makes a memory allocations for every non-empty bucket. Instead you could just make two vectors and use sentinel values (e.g. -1) for the empty buckets.


  • 0
    J

    Thanks. It is really more efficient. :)


  • 0
    S

    nice implementation


Log in to reply
 

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