leetcode136.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?

如何在使用O(n)的时间复杂度和O(0)的额外空间复杂度来找到一个数组中唯一一个成单的数字。

思路一：hashset

可以通过set来记录数字出现的情况。如果set中不曾出现该数字，则加入set。如果已经出现，则将其从set中删除。最后无法从set中删除的数字，则是single number

1
2
3
4
5
6
7
8
9
10
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]);
    }
    int single = 0;
    for(Iterator<Integer> i = set.iterator() ; i.hasNext() ; ) single = i.next();
    return single;
}

思路二：排序

如果将array排序后，那么相同的数字一定位于相邻的位置上，只需要比较2k和2k+1位置上的值是否相同就可以了。

1
2
3
4
5
6
7
public int singleNumber2(int[] nums) {
    Arrays.sort(nums);
    for(int i = 0 ; i<nums.length-1 ; i+=2){
        if(nums[i]!=nums[i+1]) return nums[i];
    }
    return nums[nums.length-1];
}

思路三：bit manipulation

这里就需要提一下异或这个操作符。一个数值和另一个数值进行两次异或计算，该数值不变。也就是说： A XOR B XOR B = A XOR （B XOR B） = A
在这里也可以试一下具体数值。
其实异或的话，可以用白话来说就是‘要么这个，要么那个’
所以也就是说，如果将array中的所有数值都进行一次异或计算，那么最终的结果也就是那个singleNumber。

1
2
3
4
5
6
public int singleNumber3(int[] nums) {
    for (int i =1; i < nums.length; i++) {
        nums[i] ^= nums[i-1];
    }
    return nums[nums.length-1];
}