描述

题目描述

一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

示例
输入:[1,4,1,6]
返回值:[4,6]
说明:返回的结果中较小的数排在前面  
引言

首先看到这道题,抠字眼: 两个数字只出现一次,其他的数字都出现了两次,两个 “两” 是解题关键。

知识点:位运算,分治,数组,集合
难度:⭐⭐⭐


题解

解题思路
1 异或

异或的特性是:两个数字相同,则异或结果为0,两个数字不同,则其二进制位的异或结果为 1,如 4 ^ 6 = 100 ^ 110 = 010。

异或运算一般要将数字转化为二进制位,再进行运算,相同则为0,不同则为 1。

因此,看到数组里其他数字都出现两次,那么就应该联想到异或的特性,使得所有元素异或后,出现两次的数字异或都都为0。

因此异或结果后就只剩下两个只出现一次的数字,接下来问题就好解决多了。

2 分治思想,问题降维

通过与运算求出两个目标值的异或结果的最右边的 1 作为标记

通过 mark 与数组每个元素的异或结果不同,将数组分为两组,分别存放到结果集里

反正相同的两个数组都会分到同一组

两组分别异或后结果都会只下最后的两个单独数字

方法一:分治+异或

图解

image-20210623123309429

算法流程:
  • 先进行异或,结果是两个单独的数异或的结果
  • 通过与运算求出两个目标值的异或结果的最右边的 1作为标记
  • 根据 mark 将原数组分为两组,单独出现的两个数字分在不同的组
  • 返回的结果中较小的数排在前面
Java 版本代码如下:
import java.util.*;

public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        int[] ans = new int[2];
        int mark = array[0];
        // 先进行异或,结果是两个单独的数异或的结果
        // 假如array为[1,4,1,6],则 mark =1 ^ 1 ^ 4 ^ 6 = 0^4^6 = 4 ^ 6=010
        for (int i = 1; i < array.length; i++) {
            mark ^= array[i];
        }
        // 通过与运算求出两个目标值的异或结果的最右边的 1作为标记
        // 如 mark = 010-010&001=010,只保留最右边的1作为mark
        mark -= mark & (mark - 1);
        for (int i = 0; i < array.length; ++i) {
            //根据mark将原数组分为两组,单独出现的两个数字分在不同的组
            if((mark & array[i]) == 0) {
                ans[0] ^= array[i];
            } else {
                ans[1] ^= array[i];
            }
        }
        // 题目要求,返回的结果中较小的数排在前面  
        if(ans[0] > ans[1]) {
            int temp = ans[0];
            ans[0] = ans[1];
            ans[1] = temp;
        }      
        return ans;
    }
}
Python 版本代码如下:
class Solution:
    def FindNumsAppearOnce(self , array ):
        # write code here
        ab = 0
        # 进行异或,结果是两个单独的数异或的结果
        for item in array:
            ab = ab ^ item
        sep = 1
        while sep & ab == 0:
            sep = sep << 1

        a, b = 0, 0
        for item in array:
            # //根据mark将原数组分为两组,单独出现的两个数字分在不同的组
            if item & sep:
                a = a^item
            else:
                b = b^item
        # 题目要求,返回的结果中较小的数排在前面  
        return [a, b] if a < b else [b, a]
复杂度分析:

时间复杂度O(N):位运算时需要遍历数组所有元素,N 为数组长度
空间复杂度O(1):只用到了常量级别的整形数据

总结:掌握位运算的特性对于解决一些难题无往不利

方法二:集合

算法流程:
  • Java 的 Set 或 Python 中的元组 + 字典,通过出现次数保存只出现一次的结果集
  • 如果 Set 中有这个值,说明重复了,则删除 set 中该数字,保证 set 中数字都是唯一
  • 若第一次出现,加入集合中
  • 只出现一次,则加入结果集
Java 版本代码如下:
import java.util.*;
public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        // 升序排序
        TreeSet<Integer> set = new TreeSet<>((o1, o2) -> o1 - o2);
        int[] res = new int[2];
        for (int i = 0; i < array.length; ++i) {
              // 如果 Set 中有这个值,说明重复了 
            if (set.contains(array[i])) {  
                // 有重复值,则删除 set 中该数字,保证 set 中数字都是唯一
                set.remove(array[i]);    
            } else {
                // 若第一次出现,加入集合中
                set.add(array[i]);    
            }
        }
        int index = 0;
        for (Integer i : set) {
            res[index++] = i;
        }
        return res;
    }
}
Python 版本代码如下:
class Solution:
    def FindNumsAppearOnce(self , array ):
        # 字段的value存放数字出现次数
        d = {}
        li = []
        # 将给定数组当作键值 
        for i in range(len(array)):
            # 根据制定键返回相应的值,设置默认值为0
            d[array[i]] = d.get(array[i], 0) + 1
            # 返回字典的键值对组成的元组格式
        for key, value in d.items():
            # 只出现一次
            if value == 1:
                li.append(key)
        return li
复杂度分析:

时间复杂度 O(NlogN):for 循环内的 TreeSet 操作的时间复杂度为 logN
空间复杂度 O(N):用到集合、字典等数据类型,N 为数组长度

相似题目:整数中1出现的次数(从1到n整数中1出现的次数)