leetCode Missing Number

 最近因為面試解了不少前測，爬文章的時候看到這題有蠻多想法的， leetCode 會計算花費的運算時間覺得有趣，就研究了一下。

題目是 0~N 的整數陣列，中間缺了哪一個數？

一開始想到用排好再計算差值的方法

 const array = [3, 0, 1];

 const missnumber = nums => {

        array

          .sort((a, b) => a - b)

          .map((item, index) => item - array[index - 1])

          .find(item => item > 1);

        return missnumber;

      };

missnumber(array)

覺得有點多行，感覺應該有什麼很酷的方法不用反覆對陣列操作，就找了一下，發現可以用XOR 運算。

原理是 a ^ b ^ c ^ a ^ b = a ^ a ^ b ^ b ^ c = 0 ^ 0 ^ c = c

 const array = [3, 0, 1];

 const missNumber = nums => {

        const nArray = [];

        for (let i = 0; i < nums.length + 1; i++) {

          nArray.push(i);

        }

        const mathArray = nums.concat(nArray);

        const outputNumber = mathArray.reduce((total, e) => total ^ e);

        return outputNumber;

      };

 missNumber(array);

於是改了一種寫法，就程式的行數而言下面比較長，效能而言由於我家網路莫名其妙，兩者互有快慢比不出來，未來要仔細研究一下時間複雜度的計算。

參考資料：https://www.ruanyifeng.com/blog/2021/01/_xor.html