leetcode 剑指 Offer 56

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

2 <= nums.length <= 10000

解法：

思路参考：

如果出现一次的数字只有一个，那么对所有的数字进行异或，那最后的结果肯定就是这个数字，因为出现两次的数字都抵消了, 但是这里出现一次的数字有两个，那我就考虑把数组分成两个子数组，每个子数组中含有一个出现一次的数字，对每个子数组再进行刚才的异或操作就可以分别求出在改组出现次数为一的数字了

过程如下：

1. 用0和所有元素进行异或运算，得到两个只出现一次的数字的异或结果

2. 找到这个结果值中二进制中某个为1的位,必定存在这样一个位，因为如果不存在的话说明两个只出现一次的数字相等，这显然不符合题意

3. 根据刚才找到的位为1的位，让这个数字和数组中每个元素做与运算，根据得到的结果是0还是1可以把数组分成两个类，分别使用一个变量对两种

情况的元素进行异或，最后两个变量的结果就是出现了一次的数字

 1 class Solution {
 2     public int[] singleNumbers(int[] nums) {
 3 
 4         int ret = 0;
 5         int len = nums.length;
 6         // 1. 用0和所有元素进行异或运算，得到两个只出现一次的数字的异或结果
 7         for(int i = 0; i < len; i++){
 8             ret ^= nums[i];
 9         }
10         // 找到ret中为1的位
11         int n = 1;
12         while((ret & n) == 0){
13             n <<= 1;
14         }
15         // 3. 根据刚才找到的位为1的位，让这个数字和数组中每个元素做与运算，根据得到的结果是0还是1可以把数组分成两个类，分别使用一个变量对两种
16         // 情况的元素进行异或，最后两个变量的结果就是出现了一次的数字
17         int a = 0, b = 0;
18         for(int i = 0; i < len; i++){
19             if((nums[i] & n) == 0){
20                 a ^= nums[i];
21             }else{
22                 b ^= nums[i];
23             }
24         }
25         return new int[]{a, b};
26     }
27 }

leetcode 运行时间为2ms,空间为40.8mb

复杂度分析：

时间复杂度：一共三个循环，第一个和第三个是遍历了整个数组，分别花费的时间为O(n)，第二个循环为找到n中一的位置，但是循环次数最多是31位，所以花费的时间是常量级的，所以为O(1), 所以整体时间复杂度为O(2n)

空间复杂度：只需要几个局部变量，所以空间复杂度为O(1)