136. Single Number

发表于 | 分类于 | 阅读次数

Description

这里一共给出三道题

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

  2. Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
    Note:
    Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

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

题解

第一道没什么好说的，直接使用异或就可以，两个相同的数异或的结果就是0，那么剩下只出现一次的数就是我们要返回的结果

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

第二道题比较难，看了一下discuss上的解答，以赞最高的为例Challenge me , thx
排第二的写的好详细，我是看不下去的，给出链接：
https://discuss.leetcode.com/topic/11877/detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers
这里要用到类似的状态转移图，因为是3次，也就是说用两个二进制就可以表示，即00，01，10，11这其中选择三个即可，这里选择这样的状态转移图:
00(0)->10(1)->01(2)-00(3/0)
其中括号内表示的是出现的次数，我们要求出现3次的结果和出现0次的结果相同，而出现一次的结果是10，出现两次的结果是01【这里所说的01都针对每一位来说的】，用两个变量来维持这个变化，这两个变量都要对数组中的元素进行异或，而变量变化的的过程只能是这样的：
当第二个变量的第i位为0时，第一个变量的第i位才可能变为1
当第一个变量的第i位为0时，第二个变量的第i位才可能变为1
如果第一个变量的第i位为1了，说明某个数字出现了第一次，此时第二个变量第i位虽然异或结果为1，但是要满足上面两点，结果只能是0，这样就是第而个状态(10)；当该数字出现第二次的时候，此时第1个变量的第i位变为0了，那么第二个变量的第i位由于之前的0，此时再异或，而且满足条件，就变为1了，这样就到了第三个状态(01)；当这个数字出现第3次时，由于第二个变量的第i位为1，那么不满足条件，第一个变量的第i位为0，第二个变量的第i位为1，再次异或后变为0，这样就到了第4个状态(00)，也就是第一个状态；最后返回第一个状态的值即可。

1
2
3
4
5
6
7
8
9
public static int singleNumber(int[] nums) {
    int ones=0;
    int twos=0;
    for(int i=0;i<nums.length;i++){
        ones=(ones^nums[i])&~twos;
        twos=(twos^nums[i])&~ones;
    }
    return ones;
}

第三道题的关键是如何分割数组，使得这两个数字分在不同的数组中，再用第一道题的方法就可以解决
如果将题目中的数字全部异或，得到的结果是出现一次的两个数字的异或结果，由于这两个数字不相等，那么异或的结果必然大于0，也就是说二进制表示一定存在1，获取从后向前遍历得到第一个1的位置（这个1必然由0和1异或得到，也就是说通过此位必然可以区分这两个数字），将全部的数字转为二进制，在此位为1的分为一组，为0的分为另外一组，这样就解决了上面的问题，那么也就得到了这两个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] singleNumber(int[] nums) {
    int temp=0;
    int index;
    int []res=new int[2];
    for(int i=0;i<nums.length;i++){
        temp^=nums[i];
    }
    String s=Integer.toBinaryString(temp);
    index=s.length()-1;
    while(index>=0&&s.charAt(index)=='0')index--;
    index=s.length()-index;
    for(int i=0;i<nums.length;i++){
        s=Integer.toBinaryString(nums[i]);
        if(index>s.length()||s.charAt(s.length()-index)=='0')res[0]^=nums[i];
        else res[1]^=nums[i];
    }
    return res;
}

如果觉得有帮助，给我打赏吧！