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$,否则便不起作用。 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用,请随意赞赏