136.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

思路：
首先给定了一个非空整数数组，求只出现一次的那个元素
1.我们首先可以想到用HashSet来添加元素，如果元素第二次遍历到，那我们就从集合中删除它，所以到最后集合中就只剩下了那个只出现一次的元素

2.我们用HashMap也同样可以解决这个问题，我们让Map的key为数组中的元素，value来记录对应元素出现的次数，最后我们只需要找到value为1的对应的key

3.使用位运算解决，我们都知道当一个数与它本身进行异或操作最后的结果为0，所以我们定义一个变量初始化为0，然后循环遍历用这个变量异或数组中的每一个元素，最后所得结果即为只出现一次的元素。

代码实现：
	方法一（HashSet）
         HashSet<Integer> hs = new HashSet();
         for (int i = 0; i < nums.length; i++){
             if (!hs.add(nums[i])){
                 hs.remove(nums[i]);
             }
         }
         return hs.iterator().next();
         
   方法二（HashMap）
        HashMap<Integer, Integer> hm = new HashMap();
        for (Integer i : nums){
            if (hm.get(i) == null){
                hm.put(i, 1);
            }else {
                hm.put(i, hm.get(i) + 1);
            }
        }
        Set<Integer> set = hm.keySet();
        for (Integer i : set){
            if (hm.get(i) == 1){
                return i;
            }
        }
        return -1;
        
	方法三(按位异或)
        int count = 0;
        for (int i : nums){
            count ^= i;
        }
        return count;

137. 只出现一次的数字 II

说明：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

示例 1:
输入: [2,2,3,2]
输出: 3

示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99

思路：
题目规定除了某个元素出现了一次外，其余每个元素都出现了三次，所以我们使用位运算的时候应该使用两个元素来记录状态的转化

首先使用了两个变量Once与Twice，表示碰到相同元素的次数，第一次碰到一个元素，将它赋给Once，第二次遇到这个元素时，将它赋给Twice，当第三次碰到这个元素时，将Once和Twice都清空。

(假设x为某一个重复出现的元素)
当Once是x的时候，我们需要将0赋给Twice，但是Twice^x=x,所以我们通过 x & ~x 来让Twice为0
所以可以写成Twice = (Twice ^ x) & ~Once;

以示例中的[2,2,3,2]为例：

我们在循环数组的时候，首先会遇到第一个2

Once = (Once ^ 2) & ~Twice;   //由于Twice初始化为0，所以Once的值为2
Twice = (Twice ^ 2) & ~Once;  //~Once值为1101，与Twice进行与操作Twice的结果为0

第二次循环遇到的还是2

Once = (Once ^ 2) & ~Twice;   //~Twice值为1111，Once^2值为0，所以Once结果为0
Twice = (Twice ^ 2) & ~Once;  //Twice与2异或结果为2，由于Once为0，所以Twice结果为2

第三次循环遇到3

Once = (Once ^ 3) & ~Twice;   //~Twice的值为1101，Once^3值为0011，最后Once值为0001
Twice = (Twice ^ 3) & ~Once;  //~Once的值为1110，Twice^3值为0001，最后Twice值为0

第四次循环遇到2

Once = (Once ^ 2) & ~Twice;   //~Twice的值为1111，Once^2值为0011，最后Once值为0011
Twice = (Twice ^ 2) & ~Once;  //~Once的值为1100，Twice^2值为0010，最后Twice值为0

最终返回Once就是只出现一次的数

代码如下：

public int singleNumber(int[] nums) {
         int Once = 0, Twice = 0;

    for (int num : nums) {
      Once = (Once ^ num) & ~Twice ;
      Twice = (Twice ^ num) & ~Once ;
    }

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

思路：
首先给定了一个整数数组，求出现一次的那两个元素

首先我们可以使用一个HashSet来解决，将数组中的元素逐一添加到集合中，如果遇到了相同的元素，则删除，最终集合中剩余的两个元素就是只出现过一次的元素。
我们还可以使用HashMap来解决这个问题，我们用key来保存数组中的元素，用value来保存元素出现过的次数，最终我们只需要找到value为1对应的key即可
采用位运算，当我们使用异或的时候，我们都知道，相同的两个数异或的结果为0，我们用一个变量遍历整个数组，最终的结果就是那两个只出现过一次的两个元素经过异或的结果，由于这两个元素的值不相同，所以异或的结果至少有一位为1，我们只需要找到这个位，通过这个位按取0和取1来将整个数组中的元素分为两个部分，分别进行异或，最终这两个部分分别异或完的结果即为所求结果。

代码实现
	解法一：(HashSet)
        int[] arr = new int[2];
        int k = 0;
        HashSet<Integer> hs = new HashSet<>();
        for (int i : nums){
            if (!hs.add(i)){
                hs.remove(i);
            }
        }
        System.out.println(hs);
        Iterator<Integer> iterator = hs.iterator();
        while (iterator.hasNext()){
            arr[k++] = iterator.next();
        }
        return arr;

	解法二：(HashMap)
        创建一个容纳两个单独数字的数组
        int[] arr = new int[2];
        int k = 0;
        HashMap<Integer, Integer> hm = new HashMap();
        for (int i : nums){
            hm.put(i, hm.getOrDefault(i, 0) + 1);
        }
        System.out.println(hm);
        for (int i : nums){
            if (hm.get(i) == 1){
                arr[k++] = i;
            }
        }
        return arr;
        
     解法三：(异或)
		int k = 0;
        for(int i : nums){
            k ^= i;
        }
        int mark = k & (-k);位与所剩恰为最低位
        int a = 0;
        int b = 0;
        for(int i : nums){
            if((i & mark) == 0){
                a ^= i;
            }else{
                b ^= i;
            }
        }
        return new int[]{a,b};

mark = k & (-k);按位与所剩恰为最低位的验证：
我们都知道，计算机中数据以补码来进行运算，正数的补码是它本身，负数的补码按位取反再加1
例：

我们以二进制的8为例：8的二进制表示形式为0000 1000 —> -8的二进制表示为1000 1000
当我们要计算 8 & （-8）的结果时，需要转换成补码的形式
所以8的表示形式不变，而-8反码的结果是1111 0111 补码的结果是1111 1000
我们可以发现，最低位1右边所有的0在进行取反操作的时候都被置为了1，所以当我们再对反码加1操作的时候，不难发现，正数与负数的最低位1在同一位上，所以我们进行 & 操作的结果就是这个数的最低为。
>>结果为：8 & （-8） = 0000 1000

getOrDefault:如果map中含有指定的key，就返回该key对应的value，否则使用该方法的第二个参数作为默认值返回

剑指Offer56-II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：
输入：nums = [3,4,3,3]
输出：4

示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31

思路：
这里我们还是沿用位运算的思路，如果一个数字出现三次，那么它的二进制表示的每一位 (0 或 1)也出现三次，如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被3整除

代码

public int singleNumber(int[] nums) {
    int res = 0;
    //int类型有32位，统计每一位1的个数
    for(int i = 0; i < 32; i++){
        int count = 0;
        //统计第i位中1的个数
        for(int j = 0; j < nums.length; j++){
            count += (nums[j] >>> i) & 1;
        }

        if(count % 3 == 1){
            res |= 1 << i;
        }
    }
    return res;
}

原文链接：https://blog.csdn.net/m0_46132054/article/details/107701511