LeetCode-Single NumberI II III

r囧r小猫 2022-08-04 04:27 119阅读 0赞

**I)**

Given an array of integers, every element appears twice except for one. Find that single one.

Note:  
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

第一个比较好求解，异或操作就可以了：

public int singleNumber(int[] nums) {
            for (int i = 1; i < nums.length; i++) {
    			nums[0] ^= nums[i];
    		}
    		return nums[0];
        }

**III)**

在看第三个，第三个跟第一个的关系比较密切：

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?

这个可以跟第一个联想，唯一不同的就是这个有两个数字出现一次。所以现在的目标就是转化到第一个，将数组分成两组，并且将两个数字分开，怎么分呢？

public int[] singleNumber(int[] nums) {
            int n = 0;
            for (int i = 0; i < nums.length; i++) n ^= nums[i];
            n &= ~(n-1);
            int[] ret = new int[2];
            
            for (int i = 0; i < nums.length; i++) {
                if ((nums[i] & n) == 0) ret[0] ^= nums[i];
                else ret[1] ^= nums[i];
            }
               
            return ret;
        }

代码如上，先求整个数组的异或，则最终等价于两个出现一次的数字异或，然后我们根据异或的结果进行分组，很显然。如果异或的二进制表示中，有一位为1，则表示。这两个数字在此位置的二进制表示是不同的。所以就可以根据这个位来进行分组，然后就把问题转化为第一个问题了！

II)

Given an array of integers, every element appears three times except for one. Find that single one.

Note:  
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

第二个，跟上面的关系不大，尽管都是位操作：

public int singleNumber(int[] nums) {
        	int cntOne = 0;
        	int number = 0;
        	for (int i = 0; i < 32; i++) {
        		cntOne = 0;
        		for (int j = 0; j < nums.length; j++) {
        			if ((nums[j] & (1 << i)) != 0) cntOne++;
        		}
        		number |= (cntOne %= 3) << i;
        	}
        	return number;
        }

对int的每一位进行遍历判断。此时遍历数组统计每个位1,出现的次数，然后对3取余数就是出现一次的那个数在本位的次数，然后将这个32个0或1组合起来！