frendguo's blog

【LeetCode】260. Single Number III

原文地址:https://leetcode.com/problems/single-number-iii/#/description

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?

一看到这个求单独存在的数,第一反应就是异或运算。然后它却又两个要求的数,所以单纯的异或是解决不了的。

我们必须将这两个要求的数分开成两组然后再分别异或就能分别找出要求的数了。那么分组的依据是什么呢?

要想将两个数区分开来,就要找这两个数的不同点。既然是位运算,或的话是肯定不行的,然后就是与运算和异或运算了。

对于与运算,我们现在不知道这两个数是什么,所以显然是不切实际的。于是就只能用异或了。

将随便两个数异或一看,发现, 异或的结果中的最低位的 第一个1就是两个数不相同的位。于是就可以开始写代码了:

static int[] SingleNumber(int[] nums)
{
	/// 分析题目发现有两个数需要取出来,所以需要将那两个数分开来
	/// 然后再分别异或 就能找出那两个数了
	/// 开始确定 mask 
	int mask = 0;
	// mask == 要求的那两个数的异或值
	foreach (int num in nums)
	{
		mask ^= num;
	}
	// mask中 最低位的 1 就是将要求两个数 分成两组的依据  
	// 所以这里是拿到最低位中的 1
	mask &= -mask;
	// mask &= ~(mask - 1);

	/// 分组分别异或
	int[] res = new int[]{0, 0};
	foreach (int num in nums)
	{
		if ((num & mask) == 0)
		{
			res[0] ^= num;
		}
		else
		{
			res[1] ^= num;
		}
	}

	return res;
}

于是就愉快的搞定啦~

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading