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?

Solution 1. xor operation(perfect implemention)

1
2
3
4
5
6
7

public int (int[] nums) {
    int result = 0;
    for(int i : nums) {
        result ^= i;
    }
    return result;
}

Solution 2. Use Set data structure(use o(n) space and o(n) time)

- 思路１： 把所有数组元素放入一个Set p,那么single number = 2 * sum(p) - sum(nums)
- 思路２： 遍历数组,如果set已存在该元素就移除它，最后只剩下single number.
1
2
3
4
5
6


for (int num : nums) {
    if (!set.add(num)) {
        set.remove(num)
    }
    return set.iterator().next();
}






Solution 3. Sort the array and search the single number(use o(n) space and sort time)


			
赞微海报分享