1. 題目

一個整型數組 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 <= 10000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

類似題目：

LeetCode 136. 只出現一次的數字（異或^）
LeetCode 137. 只出現一次的數字 II（位運算）

2. 解題

• 對數組所有的值全部異或，得到想要求的兩個數的異或值
• 找到該異或值為1的bit
• 用該bit將數組的值分成兩組來，分別求取異或值，即得2個唯一的數

class Solution { public:vector<int> singleNumbers(vector<int>& nums) {int i, XOR = 0;for(i = 0; i < nums.size(); ++i)XOR ^= nums[i];for(i = 0; i < 32; ++i){if(XOR & (1<<i))break;}int a = 0, b = 0;for(auto& n : nums){if(n&(1<<i))a ^= n;elseb ^= n;}return {a, b};} };

總結

以上是生活随笔為你收集整理的剑指Offer - 面试题56 - I. 数组中数字出现的次数（异或，分组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。