leetcode：268. Missing Number(Java)問題解答

leetcode：268. Missing Number(Java)問題解答

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;
    }
}