1. 数组中数字出现的次数

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

  1. 示例 1：
  3. 输入：nums = [4,1,4,6]
  4. 输出：[1,6] 或 [6,1]
  5. 示例 2：
  7. 输入：nums = [1,2,10,4,1,4,3,3]
  8. 输出：[2,10] 或 [10,2]

思路：

  • 个人思路：
    • 使用一个容器，比如一个Set集合（使用List也可），装载结果数
    • 使用思路：遍历给定的数组，判断Set是否含有该数，如果没有，那么添加进去；如果有，则删掉该数
    • 最后留下的就是不重复的两个数
  • 效果很一般，速度慢。
    class Solution {
  public int[] singleNumbers(int[] nums) {
      Set<Integer> set = new HashSet<>();
      for(int i=0;i<nums.length;i++){
          if(set.contains(nums[i])){
             set.remove(nums[i]);
             continue;
          }
          set.add(nums[i]);
      }
      int res[] = new int[2];
      int k = 0;
      for(Integer n : set){
          res[k++] = n;
      }
      return res;
  }
}

优秀解法:

  • 已知一个例子：
    • 当一个数组中除了某一个元素意外，其他所有元素都重复，那么这些元素依次进行异或运算，最终得到的结果就是那个不重复的元素。（利用了相同元素进行异或结果为0的特点）
  • 此题目的难度在于，一个数组中有两个不重复的元素。

  • 那么可以想到的思路就是，将两个数进行区分，一个数组分成两个小数组，两个不重复的数分别存在于两个数组之中，这样就可以按照原先的异或处理的方式找到这两个数了。

  • 难点：

    • 如果将两个数进行区分。（如何将数组切分为两个不同的数组）

  • 解决：

    • 利用异或处理的特点，数组中所有数进行异或处理之后，得到的就是目标元素 x ^ y 的结果。
    • 异或运算有一个特点：（只有相同位置的数不同才能得到1（二进制））
      • 其结果中某个为1的位，这个1表示原先的两个数的相同位置是数是不同的。
    • 想法：那么利用这里进行一个区别
    • 这时去找一个因素进行区别（找到这个位的位置）：
      • 与运算的特点：（相同位的数都为1则得到1，否则为0（二进制））
      • 拿一个为1的十进制数，与这个x^y的结果进行与运算；若结果为0，表示不是该位，则进行右移，继续进行探索，直到找到为止。
    • 已经找到因素
    • 将数组中的数进行遍历，分别与这个区别因素进行与运算，如果结果为0表示其中一个数x的区别后的数组的元素；如果结果为1，则表示另外一个数y的区别后的数组的元素.
    • 区别的不同数组的元素，让同组进行异或运算，得到的结果分别就是x，y。
      class Solution {
public int[] singleNumbers(int[] nums) {
   int x = 0,y = 0,n = 0, m = 1;
   // 找到x^y
   for(int num : nums){
       n ^= num;
   }
   // 得到区别因素m
   while((n&m)==0){
       m <<= 1;
   }
   // 区分元素,分别进行处理得到x,y
   for(int num : nums){
       if((num&m)==0){
           x ^= num;
       }else{
           y ^= num;
       }
   }
   return new int[]{x,y};
}
}