LeetCode - Algorithms - 136. Single Number

Problem

136. Single Number

Java

Hash Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> c = new HashSet<Integer>();
        for (int i : nums) {
            if (c.contains(i))
                c.remove(i);
            else
                c.add(i);
        }
        return c.iterator().next();        
    }
}

Submission Detail

  • 61 / 61 test cases passed.
  • Runtime: 8 ms, faster than 42.20% of Java online submissions for Single Number.
  • Memory Usage: 39.8 MB, less than 22.36% of Java online submissions for Single Number.

sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        final int N = nums.length;
        if (N == 1)
            return nums[0];
        if (nums[0] != nums[1])
            return nums[0];
        if (nums[N - 1] != nums[N - 2])
            return nums[N - 1];
        for (int i = 1; i < N - 1; i++) {
            if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
                return nums[i];
            }
        }
        return nums[0];       
    }
}

Submission Detail

  • 61 / 61 test cases passed.
  • Runtime: 5 ms, faster than 54.05% of Java online submissions for Single Number.
  • Memory Usage: 39.2 MB, less than 69.77% of Java online submissions for Single Number.

XOR Bitwise

n ^ n = 0

n ^ 0 = n

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int r = nums[0];
        for (int i = 1; i < nums.length; i++) {
            r = r ^ nums[i];
        }
        return r;       
    }
}

Submission Detail

  • 61 / 61 test cases passed.
  • Runtime: 1 ms, faster than 94.97% of Java online submissions for Single Number.
  • Memory Usage: 39.1 MB, less than 79.60% of Java online submissions for Single Number.

java8 stream + xor bitwise

1
2
3
4
5
class Solution {
    public int singleNumber(int[] nums) {
        return Arrays.stream(nums).reduce(0, (a, b) -> a^b);      
    }
}

Submission Detail

  • 61 / 61 test cases passed.
  • Runtime: 2 ms, faster than 55.66% of Java online submissions for Single Number.
  • Memory Usage: 39.2 MB, less than 69.77% of Java online submissions for Single Number.