[LeetCode] 268. Missing Number

轉自LeetCode

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?

<Solution>
這題不困難，運用梯形公式就可以解了

想法如下

• 因為是 0 到 n 選 n 個數出來，所以先計算 0 到 n 的總合

• 再把總和和 array 裡面每個數相減，最後的數值就是少掉的那個

code 如下

	class Solution {
	public:
	int missingNumber(vector<int>& nums) {
	int sum = nums.size() * (nums.size() + 1) / 2;
	for(const auto &n : nums) {
	sum -= n;
	}
	return sum;
	}
	};

view raw findMissingNumberInArray_1.cpp hosted with ❤ by GitHub

還有一種解法，運用到的是 Single Number 的概念

想法如下

• 因為是從 0 到 n 挑 n 個數字出來，把這 n 個數字和 1 到 n 做 XOR，這樣有出現過的數字就會被消除，剩下的就是遺失的數字

• 至於為什麼是和 1 到 n 做 XOR，而不是 0 到 n，因為如果 0 是遺失的數字，那麼 1 到 n 做完 XOR，剩下來的就會是 0 了

code 如下(參考資料)
c++

	class Solution {
	public:
	int missingNumber(vector<int>& nums) {
	int ans = 0;
	for(int i = 0; i < nums.size(); i++) {
	ans ^= (i+1) ^ nums[i];
	}
	return ans;
	}
	};

view raw findMissingNumberInArray_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun missingNumber(nums: IntArray): Int {
	var ans = 0
	for(i in nums.indices) {
	ans = ans xor nums[i] xor (i+1)
	}
	return ans
	}
	}

view raw missing_number.kt hosted with ❤ by GitHub