448.Find All Numbers Disappeared in an Array
這是leetCode第448題
題目
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
大致意思是：
給一個(gè)由1到n整數(shù)組成的數(shù)組（n為數(shù)組長(zhǎng)度），某些數(shù)字會(huì)出現(xiàn)2（可以是2次以上）次，某些數(shù)字會(huì)出現(xiàn)1次。（如果每個(gè)數(shù)字都只出現(xiàn)一次的話，數(shù)組應(yīng)該包含1～n的所有整數(shù)，因?yàn)橛行?shù)字出現(xiàn)了2次或2次以上，導(dǎo)致一些數(shù)字不能被包含在n長(zhǎng)度的數(shù)組中。）
找出1～n中，所有沒(méi)有出現(xiàn)在數(shù)組中的數(shù)字。
你能不使用額外的空間，用O(n)的時(shí)間復(fù)雜度來(lái)解決問(wèn)題嗎？你可以假設(shè)返回的數(shù)組不算額外空間。
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6] //5和6沒(méi)有包含在數(shù)組中，數(shù)組長(zhǎng)度為8。
我的思路：
哎，我使用了額外的空間，想不出不使用額外空間的算法。
1.以數(shù)組中的每個(gè)數(shù)字作為對(duì)象result的屬性和值
2.然后遍歷1到n，如果result[i]不是undefined，說(shuō)明之前數(shù)組就存在這個(gè)數(shù)字i。如果result是undefined，說(shuō)明，這個(gè)數(shù)字i，之前不在數(shù)組中。
var findDisappearedNumbers = function(nums) {
var result = [];
var n = nums.length;
var r = [];
for(var i=0;i<n;i++){
result[nums[i]]=nums[i];
}
for(i=1;i<=n;i++){
if(result[i]===undefined){
r.push(i);
}
}
return r;
};
沒(méi)有使用額外空間的算法：
下面是別人的代碼：
var findDisappearedNumbers = function(nums) {
var n = nums.length;
var res = [];
for (var i = 0; i < n; i ++){
nums[(nums[i]-1) % n] += n;
}
for (var i = 0; i <n; i ++) {
if (nums[i] < =n){
res.push(i+1);
}
}
return res;
};
算法很巧妙，思路是這樣的：
- 循環(huán)數(shù)組，(nums[ i ]-1)%n 得到的是1-n之間的整數(shù)（原始的數(shù)字，因?yàn)榭赡軙?huì)被加n），然后把這個(gè)整數(shù)對(duì)應(yīng)的數(shù)組位置的值加上n。為什么要取模，因?yàn)檫@個(gè)位置的數(shù)字很有可能會(huì)被加n，取了模得到值就是原來(lái)的數(shù)字。
這樣做的結(jié)果就是，只要數(shù)組中出現(xiàn)過(guò)的數(shù)字，該數(shù)字減1對(duì)應(yīng)的位置，都加了至少一次n( 如果某個(gè)數(shù)字出現(xiàn)多次，其對(duì)應(yīng)的位置上的數(shù)字就會(huì)被加多次n)。所以這個(gè)位置的數(shù)字就一定大于n。
2.再次循環(huán)數(shù)組，將當(dāng)前位置i的數(shù)字與n進(jìn)行比較。如果數(shù)字小于等于n，就說(shuō)明i+1不存在數(shù)組中。因?yàn)槿绻鹖+1這個(gè)數(shù)字存在數(shù)組中，那么在第一步的時(shí)候，就一定會(huì)將i（通過(guò)num[i]+=n改變）位置的數(shù)字加n。
簡(jiǎn)單的講就是，數(shù)組中存在的數(shù)字a都對(duì)將a-1位置的整數(shù)加上n。所以，數(shù)組中的整數(shù)大于n了，說(shuō)明被加了n，那么其索引+1對(duì)應(yīng)的整數(shù)就存在數(shù)組中。反之，數(shù)組中的整數(shù)小于等于n,就說(shuō)明其索引+1對(duì)應(yīng)的整數(shù)，不存在數(shù)組中。
第二種算法的思路不太直觀，一眼看去很難明白它的邏輯。盡管這樣，它確實(shí)沒(méi)有使用額外的空間。
測(cè)試下兩個(gè)算法的效率
執(zhí)行下面的代碼，來(lái)生成一個(gè)模塊Array.js，該模塊導(dǎo)出一個(gè)長(zhǎng)度為10000000的數(shù)組，數(shù)組中的整數(shù)在1到10000000之間。
node product.js
product.js文件的代碼如下：
var fs = require("fs");
var nums =[];
var boundary = 10000000;
for(var i=0;i<boundary;i++){
nums.push(Math.floor(Math.random()*boundary));
}
//轉(zhuǎn)成字符串
var str = "var array=["+nums+"];module.exports=array;";
//寫(xiě)入Array.js文件，生成了js代碼
fs.writeFile('Array.js', str, function(err) {
if (err) {
return console.error(err);
}
console.log("數(shù)據(jù)寫(xiě)入成功！");
});
使用如下代碼進(jìn)行測(cè)試：
var nums = require('./Array.js');
var start = new Date().getTime();
//這里就打印結(jié)果數(shù)組的長(zhǎng)度，因?yàn)閿?shù)組太長(zhǎng)了。
console.log('length:'+findDisappearedNumbers(nums).length);
var end = new Date().getTime();
console.log('time: '+(end - start));
第一種算法的結(jié)果如下：
length:3679312
time: 1461
第二種算法的結(jié)果如下：
length:3679312
time: 440
第二種算法的時(shí)間明顯更快。原因可能是，我的算法使用了額外的空間來(lái)儲(chǔ)存數(shù)據(jù)，每次儲(chǔ)存都需要開(kāi)辟新的內(nèi)存，或許比較耗時(shí)。而第二種是在原來(lái)的基礎(chǔ)上修改的，或許省力吧。
下面驗(yàn)證一下我的猜想
計(jì)算使用新定義的數(shù)組來(lái)儲(chǔ)存10000000個(gè)1花費(fèi)的時(shí)間,測(cè)試3次。
var nums = require('./Array.js');
var start = new Date().getTime();
var newArray = [];
for(var i=0;i<10000000;i++){
newArray[i]=1;
}
var end = new Date().getTime();
console.log('time: '+(end-start));
3次結(jié)果分別如下：
time: 238
time: 226
time: 228
計(jì)算在原來(lái)的數(shù)組上儲(chǔ)存10000000個(gè)1話費(fèi)的時(shí)間，測(cè)試3次。
var nums = require('./Array.js'); // 長(zhǎng)度為10000000
var start = new Date().getTime();
var newArray = [];
for(var i=0;i<10000000;i++){
nums[i]=1;
}
var end = new Date().getTime();
console.log('time: '+(end-start));
3次結(jié)果分別如下：
time: 70
time: 72
time: 64
結(jié)論：在原來(lái)的數(shù)組上儲(chǔ)存數(shù)據(jù)更加高效。
因此在算法中減少額外空間的使用，能提高算法的效率。
