Leetcode - Longest Consecutive Sequence

Screenshot from 2016-01-13 14:35:58.png

My code:

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        HashSet<Integer> helper = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++)
            helper.add(nums[i]);
        int len = 1;
        int longestLen = 1;
        for (int i = 0; i < nums.length; i++) {
            int tmp = nums[i];
            if (!helper.contains(tmp))
                continue;
            while (helper.contains(tmp - 1)) {
                helper.remove(tmp - 1);
                len++;
                tmp--;
            }
            tmp = nums[i];
            while (helper.contains(tmp + 1)) {
                helper.remove(tmp + 1);
                len++;
                tmp++;
            }
            helper.remove(nums[i]);
            longestLen = Math.max(longestLen, len);
            len = 1;
        }
        return longestLen;
    }
}

看了提示思路之后才寫出來(lái)。好奇怪魁衙,為什么自己想就想不出來(lái)报腔!
就是一個(gè)左右不斷合并的過(guò)程。然后不斷把已經(jīng)探明過(guò)的值從HashSet中刪除以避免重復(fù)探測(cè)剖淀。
參考網(wǎng)址:
http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/

然后還有一種 Union Find 的做法纯蛾。
我看了網(wǎng)上對(duì)該算法的解釋和Discuss里面的代碼后自己重寫了一個(gè),

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        Union union = new Union(nums.length);
        HashMap<Integer, Integer> helper = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (helper.containsKey(nums[i])) {
                continue;
            }
            helper.put(nums[i], i);
            if (helper.containsKey(nums[i] - 1))
                union.union(i, helper.get(nums[i] - 1));
            if (helper.containsKey(nums[i] + 1))
                union.union(i, helper.get(nums[i] + 1));
        }
        return union.maxUnion();
    }
    
    private class Union {
        int[] unions;
        int[] size;
        int count;
        Union(int n) {
            unions = new int[n];
            size = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                unions[i] = i;
                size[i] = 1;
            }
        }
        
        /** return the group id of this index */
        int find(int p) {
            if (p >= unions.length)
                return -1;
            while (p != unions[p])
                p = unions[p];
            return p;
        }
        
        /** test whether two indexs are connectted */
        boolean connected(int p, int q) {
            p = find(p);
            q = find(q);
            return p == q;
        }
        
        /** connect two components by making their group id equal */
        void union(int p, int q) {
            p = find(p);
            q = find(q);
            if (size[p] > size[q]) {
                size[p] += size[q];
                unions[q] = p;
            }
            else {
                size[q] += size[p];
                unions[p] = q;
            }
            count--;
        }
        
        /** return the maximum size of components */
        int maxUnion() {
            int max = 1;
            for (int i = 0; i < unions.length; i++) {
                max = Math.max(max, size[i]);
            }
            return max;
        }
    }
}

然后是Discuss里面的代碼:
https://leetcode.com/discuss/68905/my-java-solution-using-unionfound

我比他更快的原因在于纵隔,我提前做了一個(gè)size數(shù)組專門用來(lái)記錄大小翻诉,并且當(dāng)合并樹的時(shí)候可以使該算法更快。

Union Find 是普林斯頓算法第一章講的東西捌刮,當(dāng)時(shí)理解起來(lái)還有些困難∨龌停現(xiàn)在思考下,覺得這個(gè)算法的確不錯(cuò)糊啡。它解決了什么問題拄查?
當(dāng)我們需要根據(jù)value將index連接起來(lái)吁津,而index又相鄰時(shí)棚蓄,
Union Find 用代碼解決了這個(gè) ** 連接結(jié)點(diǎn) ** 的問題堕扶。
Nice Algorithm!
一個(gè)比較全面的算法講解:
http://blog.csdn.net/dm_vincent/article/details/7655764

Anyway, Good luck, Richardo!

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市梭依,隨后出現(xiàn)的幾起案子稍算,更是在濱河造成了極大的恐慌,老刑警劉巖役拴,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件糊探,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡河闰,警方通過(guò)查閱死者的電腦和手機(jī)科平,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)姜性,“玉大人瞪慧,你說(shuō)我怎么就攤上這事〔磕睿” “怎么了弃酌?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)儡炼。 經(jīng)常有香客問我妓湘,道長(zhǎng),這世上最難降的妖魔是什么乌询? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任榜贴,我火速辦了婚禮,結(jié)果婚禮上妹田,老公的妹妹穿的比我還像新娘竣灌。我一直安慰自己,他們只是感情好秆麸,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布初嘹。 她就那樣靜靜地躺著,像睡著了一般沮趣。 火紅的嫁衣襯著肌膚如雪屯烦。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天房铭,我揣著相機(jī)與錄音驻龟,去河邊找鬼。 笑死缸匪,一個(gè)胖子當(dāng)著我的面吹牛翁狐,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播凌蔬,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼露懒,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼闯冷!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起懈词,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤蛇耀,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后坎弯,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體纺涤,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年抠忘,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了撩炊。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡崎脉,死狀恐怖衰抑,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情荧嵌,我是刑警寧澤呛踊,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站啦撮,受9級(jí)特大地震影響谭网,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜赃春,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一愉择、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧织中,春花似錦锥涕、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至刁笙,卻和暖如春说搅,著一層夾襖步出監(jiān)牢的瞬間砂沛,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工面哥, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留逛揩,地道東北人毒租。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓惹谐,卻偏偏與公主長(zhǎng)得像碾篡,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子蹂喻,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容