剑指offer-40、数组中只出现⼀次的数字
<h2 id="题描述">题⽬描述</h2><p>⼀个整型数组⾥除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现⼀次的数字。</p>
<p>示例<br>
输入：<br>
输出：3，1</p>
<h2 id="思路解答">思路解答</h2>
<h3 id="哈希表统计">哈希表统计</h3>
<p>使⽤ hashmap 存储数字出现的次数， key 为出现的数字， value 为该数字出现的次数。遍历⾥⾯所有的数字，如果 hashmap 中存在，那么 value （次数）+1，如果 hashmap 中不存在,那么 value 置为1。</p>
<p>遍历完成之后，需要将次数为 1 的数字捞出来，同样是遍历 hashmap ，由于只有两个满⾜条件，我们设置⼀个标识变量，初始化为1，如果找到第⼀个满⾜条件的数字，除了写⼊放回数组中，还需要将该标识置为 2 ，表示接下来找的是第 2 个。</p>
<p>如果找到第 2 个，那么写⼊之后，直接 return 。</p>
<pre><code class="language-java">public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
Map<Integer, 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.Entry<Integer, Integer> entry : maps.entrySet()) {
if (entry.getValue() == 1) {
if (index == 1) {
num1 = entry.getKey();
index++;
} else {
num2 = entry.getKey();
return;
}
}
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要遍历数组两次</li>
<li><strong>空间复杂度</strong>：O(n)，需要HashMap存储频率信息</li>
</ul>
<h3 id="排序遍历">排序遍历</h3>
<p>先对数组排序，然后遍历查找不连续的数字。排序后相同的数字会相邻，遍历找到不连续的数字</p>
<pre><code class="language-java">public class Solution {
public int[] FindNumsAppearOnce(int[] nums) {
if (nums == null || nums.length < 2) {
return new int;
}
// 对数组进行排序
int[] sorted = nums.clone();
Arrays.sort(sorted);
int[] result = new int;
int index = 0;
// 遍历查找不连续的数字
for (int i = 0; i < sorted.length; i++) {
// 检查当前数字是否与前后都不同
boolean isSingle = true;
// 检查前一个元素（如果不是第一个元素）
if (i > 0 && sorted == sorted) {
isSingle = false;
}
// 检查后一个元素（如果不是最后一个元素）
if (i < sorted.length - 1 && sorted == sorted) {
isSingle = false;
}
if (isSingle) {
result = sorted;
if (index == 2) break; // 找到两个数字后退出
}
}
// 确保结果按升序排列
if (result > result) {
int temp = result;
result = result;
result = temp;
}
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(nlogn)，主要来自排序操作</li>
<li><strong>空间复杂度</strong>：O(1) 或 O(n)，取决于是否克隆数组</li>
</ul>
<h3 id="位运算最优解">位运算（最优解）</h3>
<p>⾸先需要了解⼀定位运算知识，异或是指⼆进制中，⼀个位上的数如果相同结果就是0，不同则结果是0.</p>
<p>也就是如果⼀个数的最低位是0，另⼀个数的最低位是0，那么异或结果的最低位是0；如果⼀个数的最低位是0，另⼀个数的最低位是1，那么异或结果的最低位是1。</p>
<p>异或操作可以交换，不影响结果：A<sup>B</sup>C = A<sup>B</sup>C</p>
<p>A^A=0,任何⼀个数异或⾃身，等于0，因为所有位都相同</p>
<p>A^0 = A，任何⼀个数异或0，等于⾃身，因为所有位如果和0不同，就是1，也就是保留了⾃身的数值</p>
<p>假设⾥⾯出现⼀次的两个元素为 A 和 B ，初始化异或结果 res 为0，遍历数组⾥⾯所有的数，都进⾏异或操作，则最后结果 res = A^B 。</p>
<p>但是我们拿到这个 A 和 B 异或之后的结果，怎么区分呢？</p>
<p>有⼀种巧妙的思路，因为 A 和 B 的某⼀位不同才会在结果中出现 1 ，说明在那⼀位上， A 和 B 中肯定有⼀个是 0 ，有⼀个是 1 。</p>
<p>那我们取出异或结果 res 最低位的1，假设这个数值是 temp （temp只有⼀个位是1，也就是A和B最后不同的位）</p>
<p>遍历数组中的元素，和 temp 进⾏与操作，如果和 temp 相与，不等于0。说明这个元素的该位上也是1。那就说明它很有可能就是 A 和 B 中的⼀个。</p>
<p>只是有可能，其他的数也有可能该位上为 1 。但是符合这种情况的，其他数肯定出现两次，⽽ A 和 B只可能有⼀个符合，并且只有可能出现⼀次 A 或者 B 。</p>
<p>凡是符合和 temp 相与,结果不为0的，我们进⾏异或操作。</p>
<p>也就是可能出现， res1 = B<sup>C</sup>D<sup>C</sup>D...<sup>E</sup>E^B 或者 res1 = A<sup>C</sup>D<sup>C</sup>D...<sup>E</sup>E 。</p>
<p>上⾯的式⼦可以视为 res1 = B 或者 res1 = A</p>
<p>这样操作下来，我们就知道了 res1 肯定是其中⼀个只出现⼀次的数（ A 或者 B ）,⽽同时上⾯计算出了 res = A^B ,也就是可以通过 res1^res 求出另⼀个数。</p>
<pre><code class="language-java">public 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 = res1;
// 求出另外⼀个数
num2 = res ^ res1;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，只需要遍历数组两次</li>
<li><strong>空间复杂度</strong>：O(1)，只使用固定数量的变量</li>
</ul>
<h4 id="位运算原理解析">位运算原理解析</h4>
<p>通过示例详细解释算法过程：</p>
<p><strong>输入</strong>：<code></code><br>
<strong>单次数</strong>：3 和 1</p>
<p><strong>步骤1：计算所有数字的异或结果</strong></p>
<pre><code class="language-java">92 ^ 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
</code></pre>
<p><strong>步骤2：找到异或结果的最低位的1</strong></p>
<pre><code class="language-java">3的二进制: 0011
1的二进制: 0001
3^1=2的二进制: 0010
最低位的1在从右往左第2位（值为2）
</code></pre>
<p><strong>步骤3：根据最低位1分组</strong></p>
<ul>
<li><strong>第1组（第2位为0）</strong>：3(0011), 43(101011), 54(110110), 1(0001), 92(1011100)</li>
<li><strong>第2组（第2位为1）</strong>：2(0010)</li>
</ul>
<p><strong>步骤4：分别异或各组</strong></p>
<pre><code class="language-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位为0）：3, 1// 只有这两个数在第2位为0且是单次数
第2组（第2位为1）：所有其他数
正确的计算：
第1组: 3 ^ 1 = 2
第2组: 92 ^ 43 ^ 54 ^ 92 ^ 43 ^ 2 ^ 2 ^ 54 = 0
</code></pre>
<p><strong>位运算特性利用：</strong></p>
<ul>
<li>相同数字异或为0：<code>a ^ a = 0</code></li>
<li>任何数与0异或为本身：<code>a ^ 0 = a</code></li>
<li>异或满足交换律和结合律</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19226259
頁:
[1]