答疑坊 程设/离散/DSA 趣题若干

发表于 更新于 分类于 ， 阅读次数： 本文字数： 147 阅读时长 ≈ 1 分钟
答疑坊答疑遇到的一些比较有趣的程设/离散/DSA题目

P1

问题描述

输入 \(3n-1\) 个数，其中 \(n-1\) 个数出现恰好 \(3\) 次，\(1\) 个数恰好出现 \(2\) 次。求这个出现 \(2\) 次的数。

要求，时间复杂度 \(\tilde {\mathcal O}(n)\) , 空间复杂度 \(\mathcal O(1)\) .

算法分析

考虑使用三进制不进位加法，显然满足交换律、结合律，且 \(a\oplus a\oplus a=0\) ，出现 \(3\) 次的数都抵消掉，只剩下恰好出现 \(2\) 次的那个数 \(a\) 的 "2倍"。

对最后结果 \(sum\) 求 \(sum\oplus sum\) 。因 \(sum=a\oplus a\) , 故 \(sum\oplus sum=a\oplus a\oplus a\oplus a=a\) 。