A summary of Java solutions

• ``````    A summary of solutions, the first two are learned and modified from previous answer with detailed explanation.
The third one is wrote for fun since I wrote the similar method for single number II for fun as well.

public class Solution {
public int[] singleNumber(int[] nums) {
// go through the array and XOR every element, for example, result = 6 (3^5)
int result = nums[0];
for(int i = 1; i < nums.length; i++){
result ^= nums[i];
}
// notice that 6^5 = 3, 6^3 = 5
// now how to find 3 and 5 from 6
int[] r = new int[2];
// find the lowest bit of the result
// let's say 6 (0110), -6 = 1010  0110 & 1010 = 0010
int lowbit = result & -result;
// since this bit from the result is 1, we can be sure that
// a & lowbit and b & lowbit have different result
for(int n : nums){
if((n & lowbit) == 0) r[0] ^= n;
else r[1] ^=n;
}
return r;
}
}

public class Solution {
public int[] singleNumber(int[] nums) {
HashSet<Integer> h = new HashSet<>();
for(int n : nums){
if(h.contains(n)) h.remove(n);
}
Object[] t =h.toArray();
int[] result = new int[2];
result[0] = (int)t[0];
result[1] = (int)t[1];
return result;
}
}

public class Solution {
public int[] singleNumber(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
int[] result = new int[2];
for(int i = 0; i < len; ){
if(i != len - 1 && nums[i] == nums[i+1]) i += 2;
else{
if(result[0] == 0) result[0] = nums[i];
else result[1] = nums[i];
i++;
}
}
return result;
}
}``````

• Good answers. I have a quick question about the second solution. It's not constant space, right?

• Yes, it is O(n) space. Constant space means in-place operation, but in this case a hashmap is created.

• Can you explain this comment in first solution?
// find the lowest bit of the result
// let's say 6 (0110), -6 = 1010 0110 & 1010 = 0010
Says x, why x & (-x) = lowest bit with 1?

• check the highest voted result. It has what you need.
basically it divides the group into two.

• For the second solution, I have the same thought but more concise.

``````public int[] singleNumber(int[] nums) {
int[] res = new int[2];
Set<Integer> set = new HashSet<>();
for (int n : nums) {
if(!set.add(n)) //add() will return true if no duplicate element added, return false if it is a duplicate element
set.remove(n);
}
Object[] obj = set.toArray();
res[0] = (int)obj[0];
res[1] = (int)obj[1];
return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.