描述

题目描述

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

提示：输出时按非降序排列。

示例

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

知识点：位运算, 哈希

难度：⭐⭐⭐

题解

2. 与运算, 算出异或结果的二进制位的最右的1, 作为分组的标记位 mark
3. 最后mark与每个元素进行与运算, 根据运算结果是否为 0 分两组, 同时分别两两进行与运算, 两个组的运算结果为整数中只出现一次的两个数字

方法一：运算+分组

解题思路：

对于这种题目要求的数组中的 “两个数字”, 需要快速反应到异或这样的位运算方法, 通常会用到的技巧

算法流程：

• 先进行异或，结果是两个单独的数异或的结果
• 通过与运算求出两个目标值的异或结果的最右边的 1作为标记
• 根据mark将原数组分为两组，单独出现的两个数字分在不同的组

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        int[] ans = new int[2];
        int mark = array[0];
        // 1. 先进行异或，结果是两个单独的数异或的结果
        // 假如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];
        }
        // 2. 通过与运算求出两个目标值的异或结果的最右边的 1作为标记
        // 如 mark = 010 - 010&001=010,只保留最右边的1作为mark
        mark -= mark & (mark - 1);
        for (int i = 0; i < array.length; ++i) {
	        // 3. 根据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;
    }
}

复杂度分析：

时间复杂度 $O(N)O(N)$：运算过程需要两次遍历每个元素

空间复杂度 $O(1)O(1)$：中间结果只使用了整型常量

方法二：哈希(空间复杂度不满足)

解题思路：

用哈希表统计数字出现的次数, 找出次数为 1的两个数字, 但空间复杂度不满足题意

C++ 版本代码如下：

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& a) {
        unordered_map<int, int> mp;
        vector<int> vt;
        for(auto x:a) {
        	mp[x]++;
        }
        for(auto x:a){
        	if(mp[x]==1) vt.push_back(x);
        } 
        if(vt[0]>vt[1]) return {vt[1],vt[0]};
        else return vt;
    }
};

复杂度分析：

时间复杂度 $O(N)O(N)$：需要遍历每个元素

空间复杂度 $O(N)O(N)$：需要用到map,不满足题意