Maximum Gap

Question:
http://www.lintcode.com/en/problem/maximum-gap/
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.
Answer:
class Solution {  
public:  
    int maximumGap(vector<int> &num) {  
       if (num.size() < 2) return 0;  
        int maxNum = num[0];  
        int minNum = num[0];  
        for (int x : num) {  
            maxNum = max(maxNum, x);  
            minNum = min(minNum, x);  
        }  
        int len = (maxNum - minNum) / num.size() + 1;  
        vector<vector<int>> buckets((maxNum - minNum) / len + 1);  
        for (int x : num) {  
            int i = (x - minNum) / len;  
            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;  
            }  
        }  
        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;  
    }  
};

HOW CHRIST MET A REAL NEED

第三日,在加利利的迦拿有娶亲的筵席,耶稣的母亲在那里。 (约翰福音 2:1 和合本)
On the third day a wedding took place at Cana in Galilee. Jesus' mother was there, (John 2:1 NIV)
耶稣和他的门徒也被请去赴席。 (约翰福音 2:2 和合本)
and Jesus and his disciples had also been invited to the wedding. (John 2:2 NIV)
酒用尽了,耶稣的母亲对他说:"他们没有酒了。" (约翰福音 2:3 和合本)
When the wine was gone, Jesus' mother said to him, "They have no more wine." (John 2:3 NIV)
耶稣说:"母亲(原文是妇人) ,我与你有什么相干?我的时候还没有到。" (约翰福音 2:4 和合本)
"Woman, why do you involve me?"Jesus replied. "My hour has not yet come." (John 2:4 NIV)
他母亲对用人说:"他告诉你们什么,你们就做什么。" (约翰福音 2:5 和合本)
His mother said to the servants, "Do whatever he tells you." (John 2:5 NIV)
照犹太人洁净的规矩,有六口石缸摆在那里,每口可以盛两三桶水。 (约翰福音 2:6 和合本)
Nearby stood six stone water jars, the kind used by the Jews for ceremonial washing, each holding from twenty to thirty gallons. (John 2:6 NIV)
耶稣对用人说:"把缸倒满了水。"他们就倒满了,直到缸口。 (约翰福音 2:7 和合本)
Jesus said to the servants, "Fill the jars with water"; so they filled them to the brim. (John 2:7 NIV)
耶稣又说:"现在可以舀出来,送给管筵席的。"他们就送了去。 (约翰福音 2:8 和合本)
Then he told them, "Now draw some out and take it to the master of the banquet."They did so, (John 2:8 NIV)
管筵席的尝了那水变的酒,并不知道是哪里来的,只有舀水的用人知道。管筵席的便叫新郎来, (约翰福音 2:9 和合本)
and the master of the banquet tasted the water that had been turned into wine. He did not realize where it had come from, though the servants who had drawn the water knew. Then he called the bridegroom aside (John 2:9 NIV)
对他说:"人都是先摆上好酒,等客喝足了,才摆上次的,你倒把好酒留到如今!" (约翰福音 2:10 和合本)
and said, "Everyone brings out the choice wine first and then the cheaper wine after the guests have had too much to drink; but you have saved the best till now." (John 2:10 NIV)
这是耶稣所行的头一件神迹,是在加利利的迦拿行的,显出他的荣耀来;他的门徒就信他了。 (约翰福音 2:11 和合本)
What Jesus did here in Cana of Galilee was the first of the signs through which he revealed his glory; and his disciples believed in him. (John 2:11 NIV)

Macro view of a wine glass containing alcoholic wine with a bunch of grapes
Photo by Roberta Sorge / Unsplash

The LORD is great

愿一切寻求你的,因你高兴欢喜;愿那些喜爱你救恩的,常说:当尊 神为大! (诗篇 70:4 和合本)
But may all who seek you rejoice and be glad in you; may those who long for your saving help always say, "The Lord is great!" (Psalms 70:4 NIV)
但我是困苦穷乏的; 神啊,求你速速到我这里来!你是帮助我的,搭救我的。耶和华啊,求你不要耽延! (诗篇 70:5 和合本)
But as for me, I am poor and needy; come quickly to me, O God. You are my help and my deliverer; Lord , do not delay. (Psalms 70:5 NIV)


Photo by Justin Kauffman / Unsplash

Recommend text editor : Sublime Text

A sophisticated text editor for code, markup and prose