2012.9.14 Leetcode 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

這道題首先由于不開辟其他內(nèi)存沟蔑,所以想到了先排序再尋找矫膨,首先是冒泡排序:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int min, max;
        //冒泡排序
        for(int i = 0; i< nums.size(); i++){
            for(int j = i; j<nums.size()-i; j++){
                if(nums[j] < nums[i]){
                    swap(nums[i], nums[j]);
                }else if(nums[j] > nums[nums.size()-i-1]){
                    swap(nums[j], nums[nums.size()-i-1]);
                }
            }
        }
        //在已經(jīng)排好序的數(shù)組中進(jìn)行尋找
        for(int i = 0; i < nums.size(); i+=2){
            if(i == 0&&nums[0]!=nums[1]){
                return nums[0];
                break;
            }else if(i == nums.size()-1&&nums[i]!= nums[i-1]){
                return nums[nums.size()-1];
                break;
            }
            else if(nums[i]!=nums[i+1]){
                return nums[i];
                break;
            }
        }
        return 0;
    }
    
};

但是提交上去之后,超時(shí)了

屏幕快照 2016-09-16 16.34.10.png

說明思路沒有錯(cuò)誤危尿,但是排序太慢了,嘗試掃描一半:
冒泡排序變成:

 for(int i = 0; i< (nums.size()-1)/2; i++){//這句話 變成了掃描一般
            for(int j = i; j<nums.size()-i; j++){
                if(nums[j] < nums[i]){
                    swap(nums[i], nums[j]);
                }else if(nums[j] > nums[nums.size()-i-1]){
                    swap(nums[j], nums[nums.size()-i-1]);
                }
            }
        }

提交谊娇,依舊會(huì)時(shí)間超限

上網(wǎng)查找排序時(shí)間,總結(jié)來說济欢,一般快排最快小渊,一提交法褥,果然AC酬屉,所以代碼如下
<u>Runtime: 26 ms</u>

class Solution {
public:
    vector<int> num;
    
    void quick_sort(int left, int right)
    {
        if(left<right)
        {
            int i = left;
            int j = right;
            int x = num[i];
            
            while(i<j)
            {
                while(i<j&&num[j]>x)
                    j--;
                if(i<j){
                    num[i] = num[j];
                    i++;
                }
                while(i<j&&num[i]<x)
                    i++;
                if(i<j){
                    num[j] = num[i];
                    j--;
                }
            }
            num[i] = x;
            quick_sort(left, i-1);
            quick_sort(i+1, right);
            }  
    }

    int singleNumber(vector<int>& nums) {
        num.clear();
        num = nums;
        quick_sort(0, nums.size()-1);
        for(int i = 0; i < num.size(); i+=2){
            if(i == 0&&num[0]!=num[1]){
                return num[0];
                break;
            }else if(i == num.size()-1&&num[i]!= num[i-1]){
                return num[num.size()-1];
                break;
            }
            else if(num[i]!=num[i+1]){
                return num[i];
                break;
            }
        }
        return 0;
    }
    
};

根據(jù)網(wǎng)友啟發(fā)呐萨,發(fā)現(xiàn)了一種更簡單的方法酱鸭。
由于n^n=0, 而0^n = n, 所以給定一組數(shù)組
可以將所有數(shù)進(jìn)行一起異或垛吗,最后剩下的那個(gè)數(shù)就是single num,時(shí)間復(fù)雜度為O(N)怯屉,代碼如下
時(shí)間為<u>19ms</u>

class Solution {
public:
    
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i<nums.size(); i++){
            res = res ^ nums[i];
        }
        return res;
    }
    
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末锨络,一起剝皮案震驚了整個(gè)濱河市赌躺,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌羡儿,老刑警劉巖礼患,帶你破解...
    沈念sama閱讀 217,542評論 6 504
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異掠归,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)虏冻,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,822評論 3 394
  • 文/潘曉璐 我一進(jìn)店門肤粱,熙熙樓的掌柜王于貴愁眉苦臉地迎上來厨相,“玉大人领曼,你說我怎么就攤上這事∈荆” “怎么了毁渗?”我有些...
    開封第一講書人閱讀 163,912評論 0 354
  • 文/不壞的土叔 我叫張陵单刁,是天一觀的道長。 經(jīng)常有香客問我幻碱,道長,這世上最難降的妖魔是什么褥傍? 我笑而不...
    開封第一講書人閱讀 58,449評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮喇聊,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘誓篱。我一直安慰自己朋贬,他們只是感情好窜骄,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,500評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著邻遏,像睡著了一般糠亩。 火紅的嫁衣襯著肌膚如雪准验。 梳的紋絲不亂的頭發(fā)上赎线,一...
    開封第一講書人閱讀 51,370評論 1 302
  • 那天糊饱,我揣著相機(jī)與錄音垂寥,去河邊找鬼另锋。 笑死滞项,一個(gè)胖子當(dāng)著我的面吹牛夭坪,可吹牛的內(nèi)容都是我干的蓖扑。 我是一名探鬼主播,決...
    沈念sama閱讀 40,193評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼律杠,長吁一口氣:“原來是場噩夢啊……” “哼潭流!你這毒婦竟也來了柜去?” 一聲冷哼從身側(cè)響起灰嫉,我...
    開封第一講書人閱讀 39,074評論 0 276
  • 序言:老撾萬榮一對情侶失蹤嗓奢,失蹤者是張志新(化名)和其女友劉穎讼撒,沒想到半個(gè)月后股耽,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體根盒,經(jīng)...
    沈念sama閱讀 45,505評論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡物蝙,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,722評論 3 335
  • 正文 我和宋清朗相戀三年炎滞,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了诬乞。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片册赛。...
    茶點(diǎn)故事閱讀 39,841評論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡震嫉,死狀恐怖森瘪,靈堂內(nèi)的尸體忽然破棺而出票堵,到底是詐尸還是另有隱情扼睬,我是刑警寧澤悴势,帶...
    沈念sama閱讀 35,569評論 5 345
  • 正文 年R本政府宣布痰驱,位于F島的核電站瞳浦,受9級特大地震影響担映,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜蝇完,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,168評論 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望矗蕊。 院中可真熱鬧,春花似錦傻咖、人聲如沸朋魔。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,783評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至扇雕,卻和暖如春拓售,著一層夾襖步出監(jiān)牢的瞬間镶奉,已是汗流浹背础淤。 一陣腳步聲響...
    開封第一講書人閱讀 32,918評論 1 269
  • 我被黑心中介騙來泰國打工哨苛, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留鸽凶,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,962評論 2 370
  • 正文 我出身青樓玻侥,卻偏偏與公主長得像,于是被迫代替她去往敵國和親迹缀。 傳聞我的和親對象是個(gè)殘疾皇子蜜徽,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,781評論 2 354

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

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪:刷leetcod...
    土汪閱讀 12,744評論 0 33
  • 136 SingleNumber Given an array of integers, every elemen...
    不不與閱讀 410評論 0 1
  • 為什么管理人員都喜歡用Visio畫圖盆色?其實(shí)有原因的: 在這里灰蛙,我歸納為以下幾點(diǎn): 形狀數(shù)據(jù)一體化隔躲,這是管理者最喜歡...
    小名一峰閱讀 3,306評論 0 9
  • 關(guān)于選擇摩梧,每天每時(shí)每刻都在出現(xiàn) 有關(guān)拼搏宣旱,有關(guān)勇敢仅父;有關(guān)道德,有關(guān)評判 有些東西浑吟,我們又不能選擇 關(guān)于出生,關(guān)于童...
    四月的魚閱讀 524評論 0 6
  • 今天看了一篇文章组力,題目是“二十歲,你能為父親做些什么燎字?”在看到這個(gè)題目時(shí)腥椒,我想到了很多很多答案阿宅∧穑可當(dāng)我看見那張...
    zcyyyy閱讀 374評論 1 2