題目描述
一個(gè)長(zhǎng)度為 n-1 的遞增排序數(shù)組中的所有數(shù)字都是唯一的,并且每個(gè)數(shù)字都在范圍 0 ～ n-1 之內(nèi)岖免。在范圍 0 ～ n-1 內(nèi)的 n 個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該數(shù)組中,請(qǐng)找出這個(gè)數(shù)字
題目描述
- 數(shù)字唯一
- 缺失其中一個(gè)
參數(shù)說(shuō)明
/**
* @param {number[]} nums
* @return {number}
*/
題解及實(shí)現(xiàn)
1. 二分查找
用兩指針,i 指針指向最后一位,j 指針指向第一位,考慮到只有一個(gè)數(shù)字缺失,例如[1,2,3,4],取中點(diǎn) i+j/2 = 1.5 無(wú)論取 1,還是 2,與對(duì)應(yīng)位數(shù)字相比都是小的,這說(shuō)明小數(shù)缺失,大數(shù)左移,所以將搜索范圍縮小至[j,mid-1],此例子中 j==i==0,最后比較此位,若 i>nums[i],說(shuō)明大數(shù)缺失,反之小數(shù)缺失
var missingNumber = function (nums) {
let i = nums.length - 1;
let j = 0;
let mid;
while (j <= i) {
mid = Number.parseInt((i + j) / 2);
mid === nums[mid] ? (j = mid + 1) : (i = mid - 1);
}
return j; //最后j指向的索引就是結(jié)果
};
時(shí)間復(fù)雜度:O(log(n))
- 資源使用情況
- 執(zhí)行用時(shí)：84 ms, 在所有 JavaScript 提交中擊敗了 81.44%的用戶
- 內(nèi)存消耗：40.1 MB, 在所有 JavaScript 提交中擊敗了 6.47%的用戶
2. 遍歷總和作減法
考慮到數(shù)字唯一且只缺失一個(gè),可以將數(shù)組中的整數(shù)進(jìn)行累加再被本來(lái)應(yīng)該的總數(shù)減
var missingNumber = function (nums) {
return (
(nums.length * (nums.length + 1)) / 2 - nums.reduce((a, b) => a + b, 0)
);
};
時(shí)間復(fù)雜度:O(n)
- 資源使用情況
- 執(zhí)行用時(shí)：76 ms, 在所有 JavaScript 提交中擊敗了 95.33%的用戶
- 內(nèi)存消耗：39.7 MB, 在所有 JavaScript 提交中擊敗了 13.25%的用戶
問(wèn)題:太慢了
同思路黑科技版
var missingNumber = function (nums) {
return (nums.length * (nums.length + 1)) / 2 - eval(nums.join("+"));
};
- 資源使用情況
- 執(zhí)行用時(shí)：112 ms, 在所有 JavaScript 提交中擊敗了 8.04%的用戶
- 內(nèi)存消耗：41 MB, 在所有 JavaScript 提交中擊敗了 5.03%的用戶
問(wèn)題:黑科技是用來(lái)炫技的,不是拿來(lái)用的
3. 數(shù)學(xué)思維之異或
眾所周知,相同的數(shù)異或?yàn)?0,如果將數(shù)組補(bǔ)全為 n 為,比如[0,1,2,3,4],那么其和相應(yīng)索引之間異或再相加為 0,現(xiàn)缺失了一個(gè)數(shù),但我們把索引補(bǔ)全,比如上述缺失 1,但索引補(bǔ)全為 0,1,2,3,4 他們和數(shù)組元素進(jìn)行異或的和就是 1
var missingNumber = function (nums) {
let i = 0;
let result = 0;
for (; i < nums.length; i++) result ^= i ^ nums[i];
return result ^ nums.length;
};
時(shí)間復(fù)雜度:O(n)
- 資源使用情況
- 執(zhí)行用時(shí)：80 ms, 在所有 JavaScript 提交中擊敗了 90.78%的用戶
- 內(nèi)存消耗：39.9 MB, 在所有 JavaScript 提交中擊敗了 10.86%的用戶
