A summary of Java solutions


  • 14
    K
        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);
                        else h.add(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;
                }
            }

  • 0
    C

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


  • 0
    A

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


  • 0
    L

    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?

    Thanks in advance.


  • 0
    W

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


  • 0
    J

    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;
        }    
    

Log in to reply
 

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