【Java實作】劍指Offer53.2——0~n-1中缺失的數字：面試真題，兩種思路分享
前面有另一道面試題【Java實作】劍指offer53.1——在排序陣列中查找數字（LeetCode34：在排序陣列中查找元素的起始位置）
都是二分型別的，可以借鑒一下思路
題意決議：
這道題很特別，所有的測驗用例都很有特點，都是形如[0,1,2,3,5,6,7]這樣的，突然跳躍這個數值的索引，即是問題的解
具體如下：
- 前半部分陣列中：索引和數值相等
- 后半部分陣列中：索引比數值小1
第一種：二分思想
不同于以往的二分查找，這里二分法直接比較索引、數值這兩者，來找到缺失的那個值，設索引為index，數值為nums[index]：
- 如果
nums[index] > index，則說明該index或其前方存在解（缺值） - 反之，說明解在該值的后方
因此，二分查找的步驟如下：
- 確定邊界
i,j，獲取mid索引 - 判斷
mid索引和其對應數值的關系，并參照上述步驟進行回圈 - 跳出回圈后，
i所在的索引位置即為解
二分解法代碼：
class Solution {
public int missingNumber(int[] nums) {
int i=0, j=nums.length-1;
while(i<=j) {
int mid=(i+j)>>1;
if(mid<nums[mid]) j=mid-1;
else i=mid+1;
}
return i;
}
}
第二種：異或思想
異或運算中，同一個數異或的值為0：例如：5 ^ 5 = 0；a ^ b ^ b = a
根據題意，讓陣列元素與索引進行異或，如果相同，則結果為0相互抵消，最后與長度n-1異或，由于0~n-1共n個數，存在抵消不掉的情況，最后形成形式：a ^ b ^ a；結果就是缺少的那個數b
異或解法代碼：
class Solution {
public int missingNumber(int[] nums) {
int len=nums.length;
int temp=0;
for(int i=0;i<len;i++) {
temp^=(i^nums[i]);
}
return len^temp;
}
}
復雜度分析：
- 異或：時間O(n)，空間O(1)
- 二分：時間O(logn)，空間O(1)
異或方法雖然很快，但是其復雜度是高于二分法的，在資料量很大的時候推薦使用二分法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/244267.html
標籤：java