1. Problem Description
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n
, find the one that is missing from the array.
For example,Given nums = [0, 1, 3]
return 2
.
Note:Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Tags : Array ,Math , Bit Manipulation
Difficulty: Medimum
Classification: Bit Manipulation
2. 問(wèn)題翻譯
從0~n之間取出n個(gè)不同的數(shù)字士飒，找出其中丟失的那個(gè)數(shù)嘉蕾。例如掏愁，nums = [0，1，3] ，缺失的是 2。
要求 算法時(shí)間復(fù)雜度是O(n)乡话，且只占用很少的額外空間。
3. 解題分析
在解決算法題之前耳奕，對(duì)問(wèn)題進(jìn)行準(zhǔn)確的分析是設(shè)計(jì)良好解決方案的基礎(chǔ)绑青，從題干中提取出有價(jià)值信息的能力是我們刷題鍛煉的目的之一。
0~n中取n個(gè)數(shù)屋群，找出缺失的那個(gè)數(shù)
這句話中透漏出一下幾點(diǎn)闸婴，
- 1 . 數(shù)組中元素個(gè)數(shù)為 n
- 2 . 0~n 總共有(n+1)個(gè)數(shù)，而實(shí)際只有n個(gè)芍躏，二者之間相差一個(gè)數(shù)
- 3 . 題目未指明元素是否有序
以上是能夠從題目得到關(guān)鍵信息邪乍。
對(duì)于這種題目，我們腦海里面的第一解題思路是，排序->對(duì)比庇楞，但最快的排序算法時(shí)間復(fù)雜度也是O(nlogn)榜配，不符合題目線性時(shí)間的要求。
上一個(gè)思路行不通吕晌，那么我們就要考慮別的方式蛋褥，根據(jù)第二點(diǎn)信息，等價(jià)于告訴我們睛驳，有兩個(gè)序列0~n和0~n序列的子集烙心，二者相差一個(gè)數(shù)，怎么確定少了哪個(gè)數(shù)呢柏靶？到了這個(gè)地步弃理，很明顯我們可以對(duì)兩個(gè)序列分別累加求和溃论，將前者的總和減去后者總和即是丟失的那個(gè)數(shù)屎蜓，再來(lái)看下是否滿足要求，0~n求和屬于連續(xù)自然數(shù)求和钥勋，我們可以直接套用數(shù)列公式炬转，
時(shí)間復(fù)雜度為O(1),而第二個(gè)序列求和，只能通過(guò)循環(huán)來(lái)進(jìn)行計(jì)算算灸，時(shí)間復(fù)雜度為O(n),該算法總的時(shí)間復(fù)雜度為O(n)扼劈，符合題目要求，那么剩下的就是編碼的問(wèn)題了菲驴。
思路二
題目的tag中含有bit manipulation,即本題可以采用位操作來(lái)解決荐吵，根據(jù)情況可用的位運(yùn)算，唯有XOR亦或運(yùn)算赊瞬，它的特點(diǎn)是先煎，相同為0，不同為1巧涧；那么我們可以利用這個(gè)規(guī)律去解決問(wèn)題薯蝎，對(duì)兩個(gè)序列0~n 和 0~n 的子集中的元素，依次進(jìn)行亦或運(yùn)算谤绳，之后將兩個(gè)結(jié)果再次進(jìn)行亦或占锯，那么得到結(jié)果就時(shí)第二個(gè)序列中缺少的那個(gè)元素。原因是因?yàn)閷⒁嗷虻脑磉M(jìn)行推廣缩筛，將一組數(shù)依次異或消略，若里面只有一個(gè)只出現(xiàn)一次的數(shù)，其他的數(shù)都出現(xiàn)兩次瞎抛，則最后的結(jié)果必然是那個(gè)只出現(xiàn)一次的數(shù)艺演，因此就可以得到缺少的那個(gè)元素。對(duì)于這個(gè)算法，只需要進(jìn)行兩次循環(huán)钞艇，每次循環(huán)的時(shí)間復(fù)雜度是O(n)啄寡，空間復(fù)雜度為O(1)，符合題目要求哩照。具體步驟分解如下：
- 1 . 0~n 所有元素(包括0和n) XOR挺物，記做x
- 2 . nums 所有元素XOR，從nums[0] 開(kāi)始飘弧， 結(jié)果記做y
- 3 . x 和 y 進(jìn)行 XOR识藤，最后結(jié)果返回
4. 解題方案
Solution 1：
class Solution {
public:
int missingNumber(vector<int>& nums) {
unsigned int n = nums.size();
int total = n*(n+1)/2;
for(int i = 0; i < n;++i)
total -= nums[i];
return total;
}
};
Solution 2 ：
class Solution {
public:
int missingNumber(vector<int>& nums) {
unsigned int n = nums.size();
int x = 0, y = nums[0];
for(int i = 0; i<= n; ++i)
x ^= i;
for(int i = 1; i< n; ++i)
y ^= nums[i];
return x^y;
}
};
轉(zhuǎn)載請(qǐng)注明出處： http://www.reibang.com/p/b14ca0d7ad86
