136. 只出现一次的数字

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

示例 2:
输入: [4,1,2,1,2]
输出: 4
**

137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

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

示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99


提示：

  • 1 <= nums.length <= 3 * 10
  • -2 <= nums[i] <= 2 - 1

  • nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次


    进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ ```java class Solution { public int singleNumber(int[] nums) {

    1.   //解法三：状态转换，也就是设置一种运算使得初始状态经过三个相同输入再次回到初始状态
    2.   //考虑每一位二进制，不管是否为目标值，如果该位为0，经过自定义运算后结果不变
    3.   //如果该位为1，经过自定义运算后结果为初始状态，而目标值由于只出现过一次，所以会从状态0转换到状态1
    4.   /*
    5.       除目标值外，其他值每个都出现三次
    6.       不妨设对应状态为00，01，10，含义是出现次数对3取余的结果！
    7.            a b     输入c     a b
    8. 状态0      0 0     1         0 1  取b作为返回值
    9. 状态1      0 1     1         1 0
    10. 状态2      1 0     1         0 0
    12. 状态0      0 0     0         0 0
    13. 状态1      0 1     0         0 1
    14. 状态2      1 0     0         1 0
  1.         a和b如何得来呢？ 分别 看a和b的结果里为1的情况！！！
  2.         对于状态1，输入为1，a = ~a & b & c
  3.         对于状态2，输入为0，a = a & ~b & ~c
  4.         综上： a = ~a & b & c | a & ~b & ~c
  5.         对于状态0，输入为1，b = ~a & ~b & c
  6.         对于状态1，输入为0，b = ~a & b & ~c
  7.         综上： b = ~a & ~b & c | ~a & b & ~c
  8.      */
  9.     int a = 0, b = 0;
  10.     for (int c : nums) {
  11.         int temp_a = ~a & b & c | a & ~b & ~c;
  12.         b = ~a & ~b & c | ~a & b & ~c;
  13.         a = temp_a;
  14.     }
  15.     return b;
  16.     //这道题还可以再扩展
  17.     /*
  18.     * 1. 在一个数组 nums 中除一个数字只出现 奇数(小) 之外，其他数字都出现了 奇数 次。请找出那个出现奇数(小)的数字。
  19.     * 2. 在一个数组 nums 中除一个数字只出现 奇数 之外，其他数字都出现了 偶数 次。请找出那个出现奇数的数字。
  20.     * 3. 在一个数组 nums 中除一个数字只出现 偶数 之外，其他数字都出现了 奇数 次。请找出那个出现偶数的数字。
  21.     * 4. 在一个数组 nums 中除一个数字只出现 偶数(小) 之外，其他数字都出现了 偶数 次。请找出那个出现偶数(小)的数字。
  22.     * 通用解决方法：
  23.     *   a. 哈希表
  24.     *   b. 位运算统计每一位的个数
  25.     *   c. 有限自动机
  26.     * 特别的对于第2种情况，将整个数组亦或一遍就可以得到结果
  27.     * */
  28.     //例如 2 4 找2

// int a = 0, b = 0; // for (int c : nums) { // int temp_a = a & ~b & ~c | a & b & ~c | ~a & b & c | a & ~b & c; // b = ~a & b & ~c | a & b & ~c | ~a & ~b & c | a & ~b & c; // a = temp_a; // } // return a; } }

  2. <a name="sQ06M"></a>
  3. #### [260. 只出现一次的数字 III](https://leetcode-cn.com/problems/single-number-iii/)<br />
  4. 给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 **任意顺序** 返回答案。<br /> <br />**进阶：**你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？<br /> <br />**示例 1：**<br />**输入：**nums = [1,2,1,3,2,5]<br />**输出：**[3,5]<br />**解释：**[5, 3] 也是有效的答案。
  6. **示例 2：**<br />**输入：**nums = [-1,0]<br />**输出：**[-1,0]
  8. **示例 3：**<br />**输入：**nums = [0,1]<br />**输出：**[1,0]
  10. **提示：**
  12. - `2 <= nums.length <= 3 * 10`
  13. - `-2 <= nums[i] <= 2 - 1`
  14. - 除两个只出现一次的整数外，`nums` 中的其他数字都出现两次
  16. 思路：<br />对于本题，不是求1个数字，而是两个，故不能用之前的状态机，不过哈希表方法还是能用<br />既然不是求1个数字，能不能把该数组分成两个，使这两个只出现一次的数字分开，从而变为问题136呢？<br />答：可以。
  18. - 两个不同的数字的二进制表示必定有一位不一样，通过对整个数组元素做异或运算得到这两个不同数字异或的结果
  19. - 用lowbit函数找到最低不同位idx
  20. - 根据每个数在idx位的情况将数组分为2组，分别做异或运算
  22. ```java
  23. class Solution {
  24.     public int[] singleNumber(int[] nums) {
  25.         int x = 0;
  26.         for (int v : nums)
  27.             x ^= v;
  29.         x = lowbit(x);
  30.         int c1 = 0, c2 = 0;
  31.         for (int v : nums) {
  32.             if ((v & x) == 0)
  33.                 c1 ^= v;
  34.             else
  35.                 c2 ^= v;
  36.         }
  37.         return new int[]{c1, c2};
  38.     }
  39.     int lowbit(int x) {
  40.         return x & (-x);
  41.     }
  42. }