[LeetCode] 260. Single Number III

轉自LeetCode

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

<Solution>
這題算 Single Number 的衍生

不同的地方在於，這次出現一次的數字不是一個，而是兩個

解題的主要方向還是使用 XOR

想法如下

• 因為其它出現的數字都是出現兩次，所以XOR的結果都會是0

• 而當對所有數字做完XOR後，其結果(用 allXOR 表示)等同於兩個出現一次的數字做XOR

• 而allXOR裡面是1的bits，就是兩個不同數字不重複的bits。這時候，可以透過 allXOR &= -allXOR，來得到 rightmost set bit，因為只需要一個bit，就可以來區分這兩個數字

• 對 nums 再做一次歷遍XOR並利用 rightmost set bit 來做分群，這樣就可以得到答案

code 如下(參考資料)

C++

	class Solution {
	public:
	vector<int> singleNumber(vector<int>& nums) {
	int allXOR = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
	//>> find the rightmost set bit
	allXOR &= -allXOR;
	vector<int> ans(2,0);
	//>> iterate nums to find the ans
	for(const auto &n : nums) {
	if(n & allXOR) {
	ans[0] ^= n;
	}
	else {
	ans[1] ^= n;
	}
	}
	return ans;
	}
	};

view raw singleNumberInArray3_1.cpp hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun singleNumber(nums: IntArray): IntArray {
	var allXOR = 0
	for(n in nums) {
	allXOR = allXOR xor n
	}
	//>> find the rightmost set bit
	//>> we can use this rightmost set bit to separate two numbers
	//>> because we xor all the numbers so this rightmost set bit only belongs to one number
	allXOR = allXOR and -allXOR
	val ans = intArrayOf(0,0)
	for(n in nums) {
	if((n and allXOR) > 0) {
	ans[0] = ans[0] xor n
	} else {
	ans[1] = ans[1] xor n
	}
	}
	return ans
	}
	}

view raw single_number_III.kt hosted with ❤ by GitHub