資訊專欄INFORMATION COLUMN
摘要：如果存儲空間的話，首先是很容易達(dá)到。然后要求就不能排序了，基于比較的排序最低就是了。原鏈接主要原理是應(yīng)用異或來處理。復(fù)習(xí)一下異或相同為，不同為，同或相同為，不同為。
Single Number https://oj.leetcode.com/problems/single-number/
Given an array of integers, every element appears twice except for one. Find that single one.Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
這道題需要的是線性時間并且不需要額外的存儲空間，剛開始我以為是不能有自己的中間變量，后來看論壇里討論的意思是有常量數(shù)量的存儲空間也可以，即存儲空間為O(1)，運(yùn)行時間為O(n)就行了。
剛開始想了幾種復(fù)雜度比較高的，首先如果存儲空間能為O(n)，運(yùn)行時間達(dá)到O(n)還是很容易的。
如果存儲空間O(1)的話，首先nlog(n)是很容易達(dá)到。只要對數(shù)組做一下快排nlog(n)，然后再掃描一遍，判斷每一個數(shù)字和后面的數(shù)字或前面的數(shù)字是否相同，就能找到 Single Number 。
然后要求O(n)就不能排序了，基于比較的排序最低就是nlog(n)了。最后在網(wǎng)上找到了線性的方法。
原鏈接：http://www.cnblogs.com/changchengxiao/p/3413294.html
主要原理是應(yīng)用異或來處理。復(fù)習(xí)一下異或：相同為0，不同為1，同或：相同為1，不同為0。
所以0 xor X = X, X xor X = 0，又由于異或是可交換的，所以將所有的數(shù)組元素都異或一下，出現(xiàn)兩次的都交換到一起，變成了0，最后剩下的就是 Single Number 。
public class Solution {
public int singleNumber(int[] A) {
if (A == null || A.length == 0) return 0;
int result = A[0];
for(int i = 1; i < A.length; i++){
result = result ^ A[i];
}
return result;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64079.html
摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時我在談啥？...
摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數(shù)組知識點(diǎn)。或者拉到本文最下面，添加的微信等會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
Problem A website domain like discuss.leetcode.com consists of various subdomains. At the top level, we have com, at the next level, we have leetcode.com, and at the lowest level, discuss.leetcode.com...
摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
閱讀 4716·2021-11-18 13:23
閱讀 903·2021-09-22 15:24
閱讀 1928·2021-09-06 15:00
閱讀 2630·2021-09-03 10:30
閱讀 1287·2021-09-02 15:15
閱讀 2073·2019-08-30 15:54
閱讀 3036·2019-08-30 15:44
閱讀 1457·2019-08-29 15:12
