image

Photo Credit: Pixiv - 七淵

LeetCode Solution - Single Number

Posted on   |   In   |  

https://leetcode.com/problems/single-number/

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?

Single Number I

Solution 1: With HashSet

Time Complexity: O(N^2), Space Complexity: O(N);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                set.remove(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }
}

Solution 2: With Sort Algorithm

Time Complexity: O(NlogN), Space Complexity: O(1);

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

Solution 3: With XOR Operation

reference: https://leetcode.com/discuss/94594/java-solution-time-complexity-and-space-complexity-using-xor
refernce: https://leetcode.com/discuss/85396/how-can-xor-keep-many-numbers

Time Complexity: O(N), Space Complexity: O(1);
The idea hinges on 3 properties of xor. (1) that its a commutative operation (i.e. a xor b = b xor a). (2) that something xor itself is 0. So a xor a = 0. And (3) 0 xor a = a. These three properties mean that 

a xor b xor a = a xor a xor b = 0 xor b = b.

Thus it doesn’t matter the order of the numbers. If something only occurs once it won’t get negated.

1
2
3
4
5
6
7
8
9
public class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int num : nums) {
            res ^= num;
        }
        return res;
    }
}

Single Number II

https://leetcode.com/problems/single-number-ii/
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.

Solution 1: With HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();

        //Filling up the map
        for(int i=0;i<nums.length;i++){
            if(!myMap.containsKey(nums[i])){
                myMap.put(nums[i], 1);
            }
            else{
                int temp = myMap.get(nums[i]);
                temp++;
                myMap.put(nums[i], temp);
            }
        }

        // Iterating over the map and returning the number with 
        // the value pair having a value less than 3

        Iterator it = myMap.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry pair = (Map.Entry)it.next();
            int tmpValue = (int)pair.getValue();
            int tmpKey = (int)pair.getKey();
            if(tmpValue<3){
                return tmpKey;
            }
        }
        return -1;
    }
}

Solution 2: With Bit Manipulation

For a 32-bit integer, if this integer appears three times in the input array, each digit of this integer will apppears three times. While if it only appears once in the input array, each digit of this integer will appeaars only once. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        int result = 0;
        
        for (int j = 0; j < 32; j++) {
            for (int i = 0; i < nums.length; i++) {
                if ((nums[i] & (1 << j)) != 0) {
                    count[j] ++;
                }
            }
            if (count[j] % 3 != 0) {
                result += (1 << j);
            }
        }
        
        return result;
    }
}

Single Number III

https://leetcode.com/problems/single-number-iii/
Given an array of numbers 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:

  • The order of the result is not important. So in the above example, [5, 3] is also correct.
  • Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Solution 1: With HashMap

https://leetcode.com/discuss/95580/java-easy-to-understand-solution-with-map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public int[] singleNumber(int[] nums) {

        Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();

        //Filling up the map
        for(int i=0;i<nums.length;i++){
            if(!myMap.containsKey(nums[i])){
                myMap.put(nums[i], 1);
            }
            else{
                int temp = myMap.get(nums[i]);
                temp++;
                myMap.put(nums[i], temp);
            }
        }

        //Iterating over the map and returning the number with the value pair having a value less than 3
        List<Integer> myList = new ArrayList<Integer>();
        Iterator it = myMap.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry pair = (Map.Entry)it.next();
            int tmpValue = (int)pair.getValue();
            int tmpKey = (int)pair.getKey();
            if(tmpValue<2){
                myList.add(tmpKey);
            }
        }
        int[] result = new int[2];
        for(int i=0;i<myList.size();i++){
            result[i] = myList.get(i);
        }
        return result;
    }
}

Solution 2: With XOR Operation

Use XOR for all Integer in the input array, the result is the XOR result between two number like result = 3^5. We know that 3 is not equal to 5 so that 3^5 is not eqaul to 0 and there must be one digit in 3 and 5 are not equal, for example, this digit in 3 is 0 while is 1 in 5. (if not, 3^5 will be 0)

With this property, we can divide the input array inot two groups: one group contains all integer with 0 in that digit, and the another contain all integer with 1 in that digit.

Use XOR for these two groups separately, we will get 3 and 5 separately. And then with 3^result = 5 and 5^result = 3 we will find the answer of this question.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int[] singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i];
        }
        
        int pos = 0;
        for(int i = 0; i < 15; i++) {
            if ((result & (1 << i)) != 0) {
                pos = i;
            }
        }
        int groupA = 0, groupB = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & (1 << pos)) != 0) {
                groupA ^= nums[i];
            } else {
                groupB ^= nums[i];
            }
        }
        
        int[] ans = new int[2];
        ans[0] = result ^ groupA;
        ans[1] = result ^ groupB;
        
        return ans;
    }
}

More Reference:

http://blog.sina.com.cn/s/blog_77dd9d490102vwew.html
http://blog.csdn.net/lcj_cjfykx/article/details/48531073
http://believerw.github.io/2016/04/14/Bit-Manipulation/#more