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?
Subscribe to see which companies asked this question
public class Solution { public int singleNumber(int[] nums) { int xor = 0; for(int n : nums) xor ^= n; return xor; } }
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?
Subscribe to see which companies asked this question
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:
[5, 3] is also correct.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
public class Solution { public int[] singleNumber(int[] nums) { // Pass 1 : // Get the XOR of the two numbers we need to find int diff = 0; for (int num : nums) { diff ^= num; } // Get the rightmost different bit between these two numbers. diff &= -diff; // Pass 2 : int[] rets = {0, 0}; //split the two numbers we are looking for into two groups. for (int num : nums) { if ((num & diff) == 0) // the group that has rightmost bit unset. { rets[0] ^= num; } else // the group that has rightmost bit set. { rets[1] ^= num; } } return rets; } }
136. Single Number && 137. Single Number II && 260. Single Number III
原文：http://www.cnblogs.com/neweracoding/p/5470448.html