Loading... # 只出现一次的数字 给定一个整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 这个问题是trivial的，异或一遍即可得到结果。 # 只出现一次的数字 III 给定一个整数数组 `nums`，其中恰好有**两个元素**只出现**一次**，其余所有元素均出现**两次**。找出只出现一次的那两个元素。 ## 做法 我们仍然是全部异或一次，令那两个元素为$a$和$b$会得到结果$c=a^{\wedge} b$，那么怎么拆分呢？我们可以从$c$中任取一个为$1$的位，可知在这一位上$a$和$b$是不同的，那么按照这一位为$1$还是$0$分别将原数组拆分成两组求异或和，即得答案。 --- <div class="tip inlineBlock error"> 以下内容有错误之处尚待修改！ </div> # 只出现一次的数字 II ## 题意 给你一个整数数组 `nums` ，除某个元素仅出现 **一次** 外，其余每个元素都恰出现 **三次 。** 请你找出并返回那个只出现了一次的元素。 ## 分析 容易想到原本的异或本质是二阶群上操作，那么只要找到一个三阶群就容易进行了，比如$\sin(\frac{\pi x}3)$。（<span style='color:Aquamarine'>官解是通过构建一个三阶的DFA得到的三阶群，比较复杂</span>） 那么我们就求$\sin\sum_\limits{x\in nums}\frac{\pi x}3$即可把所有出现三次的数据消去。然后逆运算一下即可得到原数，所以答案就是 $$ \frac3\pi\arcsin\left|\sin\left(\sum_\limits{x\in nums}\frac{\pi x}3\right)\right| $$ 但这样只能得到$x\mod 3$。 # 只出现一次的数字 - 魔改版 ## 题意 仍然是一个整数数组$nums$，有一个元素出现$a$次，其余所有元素均出现$b$次$(a\ne b)$，请以$\mathcal O(n)$时间和$\mathcal O(1)$额外空间求出现$a$次的元素。 ## 分析 本质上还是找一个$b$阶群，那么答案实际上就是 $$ \frac b{a\pi}*\arcsin \left|\sin\left(\sum_{x\in nums}\frac{\pi x}b\right)\right| $$ 当然，我们没有限定值域，也没有指明$a$和$b$的大小，直接这样做$arcsin$不一定是双射，那么就需要放缩一下，令$L=\max_\limits{x\in nums}x$，上式化为 $$ \frac {bL}\pi*\arcsin \left|\sin\left(\sum_{x\in nums}\frac{\pi x}{baL}\right)\right| $$ 这个就是最终答案。 这个方法需要$\frac xb$能整除$aL$，否则便不起作用。 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏