数组中只出现一次的两个数字（分治+异或）

数组中只出现一次的两个数字

http://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8

描述

题目描述

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

示例

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

引言

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

知识点：位运算，分治，数组，集合
难度：⭐⭐⭐

题解

解题思路

1 异或

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

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

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

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

2 分治思想，问题降维

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

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

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

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

方法一：分治+异或

图解

算法流程：

先进行异或，结果是两个单独的数异或的结果
通过与运算求出两个目标值的异或结果的最右边的 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