Missing Number
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?
思考:前面做過幾個算法,都是通過轉換為二進制級別的計算來解決的,今天一看到這個題目一開始也行使用相應方法來解決,可是一時沒想到好的方法。正捉急時又想到可以設定一個值,讓它等於n!,然後去除以數組中非0數,結果又發現就是設一個long型的值也只能存到48!。不過這倒是讓我靈光一閃,與其弄一個階乘出來還不如弄一個“^”來連接0到n,要知道2個相同的數異或的結果為零,因此就可以弄一個0異或到n的值來依次異或數組中的每個值,結果就是缺失的那一個數。
具體代碼(Java):
public class Solution {
public int missingNumber(int[] nums) {
int xor = 0;
for(int i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i];
}
return xor ^ nums.length;
}
}