遍历完成之后需要将次数为 1 的数字捞出来同样是遍历 hashmap 由于只有两个满⾜条件我们设置⼀个标识变量初始化为1如果找到第⼀个满⾜条件的数字除了写⼊放回数组中还需要将该标识置为 2 表示接下来找的是第 2 个。如果找到第 2 个那么写⼊之后直接 return 。javapublic void FindNumsAppearOnce(int[] array, int num1[], int num2[]) { MapInteger, Integer maps new HashMap(); if (array ! null) { for (int n : array) { Integer num maps.get(n); if (num null) { // map中不存在 maps.put(n, 1); } else { // map中已经存在 maps.put(n, num 1); } } } int index 1; for (Map.EntryInteger, Integer entry : maps.entrySet()) { if (entry.getValue() 1) { if (index 1) { num1[0] entry.getKey(); index; } else { num2[0] entry.getKey(); return; } } } }时间复杂度O(n)需要遍历数组两次空间复杂度O(n)需要HashMap存储频率信息排序遍历先对数组排序然后遍历查找不连续的数字。排序后相同的数字会相邻遍历找到不连续的数字javapublic class Solution { public int[] FindNumsAppearOnce(int[] nums) { if (nums null || nums.length 2) { return new int[0]; } // 对数组进行排序 int[] sorted nums.clone(); Arrays.sort(sorted); int[] result new int[2]; int index 0; // 遍历查找不连续的数字 for (int i 0; i sorted.length; i) { // 检查当前数字是否与前后都不同 boolean isSingle true; // 检查前一个元素如果不是第一个元素 if (i 0 sorted[i] sorted[i - 1]) { isSingle false; } // 检查后一个元素如果不是最后一个元素 if (i sorted.length - 1 sorted[i] sorted[i 1]) { isSingle false; } if (isSingle) { result[index] sorted[i]; if (index 2) break; // 找到两个数字后退出 } } // 确保结果按升序排列 if (result[0] result[1]) { int temp result[0]; result[0] result[1]; result[1] temp; } return result; } }时间复杂度O(nlogn)主要来自排序操作空间复杂度O(1) 或 O(n)取决于是否克隆数组位运算最优解⾸先需要了解⼀定位运算知识异或是指⼆进制中⼀个位上的数如果相同结果就是0不同则结果是0.也就是如果⼀个数的最低位是0另⼀个数的最低位是0那么异或结果的最低位是0如果⼀个数的最低位是0另⼀个数的最低位是1那么异或结果的最低位是1。异或操作可以交换不影响结果ABC ABCA^A0,任何⼀个数异或⾃身等于0因为所有位都相同A^0 A任何⼀个数异或0等于⾃身因为所有位如果和0不同就是1也就是保留了⾃身的数值假设⾥⾯出现⼀次的两个元素为 A 和 B 初始化异或结果 res 为0遍历数组⾥⾯所有的数都进⾏异或操作则最后结果 res A^B 。但是我们拿到这个 A 和 B 异或之后的结果怎么区分呢有⼀种巧妙的思路因为 A 和 B 的某⼀位不同才会在结果中出现 1 说明在那⼀位上 A 和 B 中肯定有⼀个是 0 有⼀个是 1 。那我们取出异或结果 res 最低位的1假设这个数值是 temp temp只有⼀个位是1也就是A和B最后不同的位遍历数组中的元素和 temp 进⾏与操作如果和 temp 相与不等于0。说明这个元素的该位上也是1。那就说明它很有可能就是 A 和 B 中的⼀个。只是有可能其他的数也有可能该位上为 1 。但是符合这种情况的其他数肯定出现两次⽽ A 和 B只可能有⼀个符合并且只有可能出现⼀次 A 或者 B 。凡是符合和 temp 相与,结果不为0的我们进⾏异或操作。也就是可能出现 res1 BCDCD...EE^B 或者 res1 ACDCD...EE 。上⾯的式⼦可以视为 res1 B 或者 res1 A这样操作下来我们就知道了 res1 肯定是其中⼀个只出现⼀次的数 A 或者 B ,⽽同时上⾯计算出了 res A^B ,也就是可以通过 res1^res 求出另⼀个数。javapublic void FindNumsAppearOnce(int[] array, int num1[], int num2[]) { // A和B异或的结果 int res 0; for (int val : array) { res ^ val; } // temp保存了两个数最后⼀个不同的位 int temp res (-res); // 保存和最后⼀个不同的位异或的结果 int res1 0; for (int val : array) { // 不等于0说明可能是其中⼀个数⾄少排除了另外⼀个数 if ((temp val) ! 0) { res1 ^ val; } } // 由于其他满⾜条件的数字都出现两次所以结果肯定就是只出现⼀次的数 num1[0] res1; // 求出另外⼀个数 num2[0] res ^ res1; }时间复杂度O(n)只需要遍历数组两次空间复杂度O(1)只使用固定数量的变量位运算原理解析通过示例详细解释算法过程输入[92,3,43,54,92,43,2,2,54,1]单次数3 和 1步骤1计算所有数字的异或结果java92 ^ 3 ^ 43 ^ 54 ^ 92 ^ 43 ^ 2 ^ 2 ^ 54 ^ 1 (92 ^ 92) ^ (43 ^ 43) ^ (2 ^ 2) ^ (54 ^ 54) ^ 3 ^ 1 0 ^ 0 ^ 0 ^ 0 ^ (3 ^ 1) 3 ^ 1 2步骤2找到异或结果的最低位的1java3的二进制: 0011 1的二进制: 0001 3^12的二进制: 0010 最低位的1在从右往左第2位值为2步骤3根据最低位1分组第1组第2位为03(0011), 43(101011), 54(110110), 1(0001), 92(1011100)第2组第2位为12(0010)步骤4分别异或各组java第1组: 3 ^ 43 ^ 54 ^ 1 ^ 92 ^ 43 ^ 54 ^ 92 (3 ^ 1) ^ (43 ^ 43) ^ (54 ^ 54) ^ (92 ^ 92) 3 ^ 1 2 ❌ 这里应该是 3 ^ 1 2但我们需要重新计算正确的分组 让我们重新正确分组计算 实际分组应该是 第1组第2位为03, 1 // 只有这两个数在第2位为0且是单次数 第2组第2位为1所有其他数 正确的计算 第1组: 3 ^ 1 2 第2组: 92 ^ 43 ^ 54 ^ 92 ^ 43 ^ 2 ^ 2 ^ 54 0
key 为出现的数字， value 为该数字出现的次数。遍历⾥⾯所有的数字，如果 hashmap 中存在，那么 value （次数）+1，如果 hashmap 中不存在,那么 value 置为1。
遍历完成之后需要将次数为 1 的数字捞出来同样是遍历 hashmap 由于只有两个满⾜条件我们设置⼀个标识变量初始化为1如果找到第⼀个满⾜条件的数字除了写⼊放回数组中还需要将该标识置为 2 表示接下来找的是第 2 个。如果找到第 2 个那么写⼊之后直接 return 。javapublic void FindNumsAppearOnce(int[] array, int num1[], int num2[]) { MapInteger, Integer maps new HashMap(); if (array ! null) { for (int n : array) { Integer num maps.get(n); if (num null) { // map中不存在 maps.put(n, 1); } else { // map中已经存在 maps.put(n, num 1); } } } int index 1; for (Map.EntryInteger, Integer entry : maps.entrySet()) { if (entry.getValue() 1) { if (index 1) { num1[0] entry.getKey(); index; } else { num2[0] entry.getKey(); return; } } } }时间复杂度O(n)需要遍历数组两次空间复杂度O(n)需要HashMap存储频率信息排序遍历先对数组排序然后遍历查找不连续的数字。排序后相同的数字会相邻遍历找到不连续的数字javapublic class Solution { public int[] FindNumsAppearOnce(int[] nums) { if (nums null || nums.length 2) { return new int[0]; } // 对数组进行排序 int[] sorted nums.clone(); Arrays.sort(sorted); int[] result new int[2]; int index 0; // 遍历查找不连续的数字 for (int i 0; i sorted.length; i) { // 检查当前数字是否与前后都不同 boolean isSingle true; // 检查前一个元素如果不是第一个元素 if (i 0 sorted[i] sorted[i - 1]) { isSingle false; } // 检查后一个元素如果不是最后一个元素 if (i sorted.length - 1 sorted[i] sorted[i 1]) { isSingle false; } if (isSingle) { result[index] sorted[i]; if (index 2) break; // 找到两个数字后退出 } } // 确保结果按升序排列 if (result[0] result[1]) { int temp result[0]; result[0] result[1]; result[1] temp; } return result; } }时间复杂度O(nlogn)主要来自排序操作空间复杂度O(1) 或 O(n)取决于是否克隆数组位运算最优解⾸先需要了解⼀定位运算知识异或是指⼆进制中⼀个位上的数如果相同结果就是0不同则结果是0.也就是如果⼀个数的最低位是0另⼀个数的最低位是0那么异或结果的最低位是0如果⼀个数的最低位是0另⼀个数的最低位是1那么异或结果的最低位是1。异或操作可以交换不影响结果ABC ABCA^A0,任何⼀个数异或⾃身等于0因为所有位都相同A^0 A任何⼀个数异或0等于⾃身因为所有位如果和0不同就是1也就是保留了⾃身的数值假设⾥⾯出现⼀次的两个元素为 A 和 B 初始化异或结果 res 为0遍历数组⾥⾯所有的数都进⾏异或操作则最后结果 res A^B 。但是我们拿到这个 A 和 B 异或之后的结果怎么区分呢有⼀种巧妙的思路因为 A 和 B 的某⼀位不同才会在结果中出现 1 说明在那⼀位上 A 和 B 中肯定有⼀个是 0 有⼀个是 1 。那我们取出异或结果 res 最低位的1假设这个数值是 temp temp只有⼀个位是1也就是A和B最后不同的位遍历数组中的元素和 temp 进⾏与操作如果和 temp 相与不等于0。说明这个元素的该位上也是1。那就说明它很有可能就是 A 和 B 中的⼀个。只是有可能其他的数也有可能该位上为 1 。但是符合这种情况的其他数肯定出现两次⽽ A 和 B只可能有⼀个符合并且只有可能出现⼀次 A 或者 B 。凡是符合和 temp 相与,结果不为0的我们进⾏异或操作。也就是可能出现 res1 BCDCD...EE^B 或者 res1 ACDCD...EE 。上⾯的式⼦可以视为 res1 B 或者 res1 A这样操作下来我们就知道了 res1 肯定是其中⼀个只出现⼀次的数 A 或者 B ,⽽同时上⾯计算出了 res A^B ,也就是可以通过 res1^res 求出另⼀个数。javapublic void FindNumsAppearOnce(int[] array, int num1[], int num2[]) { // A和B异或的结果 int res 0; for (int val : array) { res ^ val; } // temp保存了两个数最后⼀个不同的位 int temp res (-res); // 保存和最后⼀个不同的位异或的结果 int res1 0; for (int val : array) { // 不等于0说明可能是其中⼀个数⾄少排除了另外⼀个数 if ((temp val) ! 0) { res1 ^ val; } } // 由于其他满⾜条件的数字都出现两次所以结果肯定就是只出现⼀次的数 num1[0] res1; // 求出另外⼀个数 num2[0] res ^ res1; }时间复杂度O(n)只需要遍历数组两次空间复杂度O(1)只使用固定数量的变量位运算原理解析通过示例详细解释算法过程输入[92,3,43,54,92,43,2,2,54,1]单次数3 和 1步骤1计算所有数字的异或结果java92 ^ 3 ^ 43 ^ 54 ^ 92 ^ 43 ^ 2 ^ 2 ^ 54 ^ 1 (92 ^ 92) ^ (43 ^ 43) ^ (2 ^ 2) ^ (54 ^ 54) ^ 3 ^ 1 0 ^ 0 ^ 0 ^ 0 ^ (3 ^ 1) 3 ^ 1 2步骤2找到异或结果的最低位的1java3的二进制: 0011 1的二进制: 0001 3^12的二进制: 0010 最低位的1在从右往左第2位值为2步骤3根据最低位1分组第1组第2位为03(0011), 43(101011), 54(110110), 1(0001), 92(1011100)第2组第2位为12(0010)步骤4分别异或各组java第1组: 3 ^ 43 ^ 54 ^ 1 ^ 92 ^ 43 ^ 54 ^ 92 (3 ^ 1) ^ (43 ^ 43) ^ (54 ^ 54) ^ (92 ^ 92) 3 ^ 1 2 ❌ 这里应该是 3 ^ 1 2但我们需要重新计算正确的分组 让我们重新正确分组计算 实际分组应该是 第1组第2位为03, 1 // 只有这两个数在第2位为0且是单次数 第2组第2位为1所有其他数 正确的计算 第1组: 3 ^ 1 2 第2组: 92 ^ 43 ^ 54 ^ 92 ^ 43 ^ 2 ^ 2 ^ 54 0
