136.Single Number

Posted on | In

Solution 1: accepted 237ms

Super slow! too much operations!

Time: O(n^2)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
public int singleNumber(int[] nums) {
    if (nums.length == 0) return 0;
    List<Integer> dic = new ArrayList<>();
    for (int i : nums) {
        if (!dic.contains(i))
            dic.add(i);
        else 
            dic.remove(Integer.valueOf(i));
    }
    return dic.get(0);
}

Solution 2: accepted 17ms

Though hashSet is more efficient, we can do better.

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int singleNumber(int[] nums) {
    if (nums.length == 0) return 0;
    HashSet<Integer> set = new HashSet<>();
    for (int i : nums) {
        if (!set.contains(i))
            set.add(i);
        else 
            set.remove(Integer.valueOf(i));
    }
    int result = 0;
    for (int j: set) {
        result += j;
    }
    return result;
}

Solution 3: accepted 1ms

Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
public int singleNumber(int[] nums) {
    if (nums.length == 0) return 0;
    int result = 0;
    for (int i : nums) {
        result = result ^ i;
    }
    return result;
}