leetcode 136. Single Number_136. single number hashset

目录

一、问题分析

二、代码实现

1、异或

2、HashSet

3、计数排序

---

 

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

给定一个非空整数数组，该数组除了一个元素只出现一次之外，其他元素均出现两次，找到这个只出现一次的元素。要求时间O(n)，空间O(1)

 

一、问题分析

测试用例：

Example 1:
Input: [2,2,1]
Output: 1
 
Example 2:
Input: [4,1,2,1,2]
Output: 4

异或的思路：由于A ^ A = 0， 0 ^ A = A，并且同级的异或运算是可交换的（ "(a^b)^a = (a^a)^b"就不是同级运算），因此除了待求元素之外，其他所有元素参与异或的结果为0，因此，可以遍历整个数组，将所有元素进行异或运算，结果就是该元素了。

 

二、代码实现

1、异或

class Solution {
 
    //异或
    public int singleNumber1(int[] nums) {
        int ret = 0;
        for (int i=0; i<nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }
}

2、HashSet

class Solution {
 
    //Set
    public int singleNumber2(int[] nums) {
        int ret = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int e : nums) {
            if (set.contains(e)) {
                ret = ret - e;
                set.remove(e);
            } else {
                ret = ret + e;
                set.add(e);
            }
        }
        return ret;
    }
    
}

3、计数排序

分别计算所求元素每一位的数值，这样遍历完32遍之后就可以知道该元素的具体值了。由题意可知，该元素的某一位要么是由偶数个0和奇数个1组成，要么就是由奇数个0和偶数个0组成，没有其他情况。

此方式的优势在于既可以返回索引，又可以返回元素本身。如果要返回前者，那前两种方法就没办法那么容易做到了。而且，当其他元素均出现三次时异或方法就行不通了。此方法的时间复杂度为O(n)。

class Solution {
    
    //计数排序
    public int singleNumber(int[] nums) {
        int ret = 0;
        
        //设有k个重复出现的元素，则count0 = 2*m + (0 or 1), count1 = 2*(k-m) + (1 or 0)
        int count0 = 0, count1 = 0;     //记录所有元素某一个位上的0个数量、1的数量
        
        for (int i=0; i<32; i++) {    //进行32遍遍历
            count0 = 0;
            count1 = 0;
            for (int j=0; j<nums.length; j++) {    //每一遍计算所有元素某个位上0的个数、1的个数之和
                if ((nums[j] & (1 << i)) == 0) {
                    count0 ++;
                } else {
                    count1 ++;
                }
            }
            if (count0 % 2 == 0) {  //有偶数个0，说明只出现一次的元素在1<<i位的值是1
                ret |= 1<<i;
            } else {                //否则，说明该位的值是0
                //ret |= 0;
            }
        }
        
        return ret;
    }
    
}

 

参考：

https://leetcode.com/problems/single-number/discuss/43238/Linear-time-with-no-extra-memory（计数排序）

https://leetcode.com/problems/single-number/discuss/43164/Java-solution-using-HashSet-instead-of-XOR（采用Set的简洁写法）

https://leetcode.com/problems/single-number/discuss/43275/My-linear-complexity-without-using-extra-memory-solution