给定一整数数组,其中有p种数出现了奇数次,其他数都出现了偶数次,怎么找到这p个数?

给定一长度为m的整数数组

A=\left [ a_{1},a_{2}\cdots a_{m} \right ]

,其中有p种不为0的数出现了奇数次,其他数都出现了偶数次,找到这p个数。

要求:时间复杂度不大于O(n),空间复杂度不大于O(1)。


        由于时间复杂度不大于O(n),则不能在遍历数组中嵌套遍历数组。而空间复杂度不大于O(1),则不能开辟数量上优势或等势于数组长度的内存空间。这需要将数组元素的信息压缩到一个有限的内存空间里,因此需要按位运算。

        按位异或运算⊕是具有如下性质的二元运算:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0,并且满足交换率、结合率。则0是⊕的单位元,即对于任意的二进制数a,都有a⊕0=0⊕a=a。而且a与自身互为逆元,即a⊕a=0。记

\begin{matrix} \overset{t}{\underset{i=1}{\bigoplus } }a_{i} \end{matrix}=\underset{t}{\underbrace{a_{1}\oplus a_{2}\oplus \cdots \oplus a_{t}}}

        那么,对于任意正整数k,有:

\begin{matrix} \overset{2k}{\underset{}{\bigoplus } }a \end{matrix}=\begin{matrix} \underbrace{a\oplus a\oplus \cdots \oplus a}\\ 2k \end{matrix}=\begin{matrix} \underbrace{\left ( a\oplus a \right )\oplus\left ( a\oplus a \right )\oplus \cdots\left ( a\oplus a \right ) }\\ k \end{matrix}=\begin{matrix} \underbrace{0\oplus0\oplus\cdots \oplus 0}\\ k \end{matrix}=0,

        \begin{matrix} \overset{2k+1}{\underset{}{\bigoplus } }a \end{matrix}=\begin{matrix} \underbrace{a\oplus a\oplus \cdots \oplus a}\\ 2k+1 \end{matrix}=\left (\begin{matrix} \overset{2k}{\underset{}{\bigoplus } }a \end{matrix} \right )\oplus a=a

        

        对于给定的这个题目,当p=1时,设\chi出现了2k+1次,其余的数都出现偶数次,则根据上述的结论有:

\bigoplus A=\begin{matrix} \overset{2k+1}{\underset{}{\bigoplus } }\chi \end{matrix}= \chi

        即将A中所有元素取异或运算即是此问题的解。

        当p=2时,取\bigoplus A=b,则必然b≠0,否则可以推出这两个数相等,从而产生悖论。取c=b\wedge \left (\bar{b}+1 \right )=2^{s-1},s为c的二进制表示中从后数第一个为1的位数。

        遍历集合A,使每个元素都和c做按位与运算,结果只能是0或者c。取结果为c的元素组成子集A',由于b的第s位是1,则两个目标数字不会都是A'的元素,否则经过⊕运算,s位的值是0的话,如果b中没有某位是1的数字,则b=0,从而产生矛盾。这样,就将问题转化成了在集合A'中查找只有一种非零整数出现奇数次的问题。即求出\chi _{1}=\bigoplus A'为其中的一个解。

        由于b=\chi _{1}\oplus \chi _{2},所以

\chi _{2}=\chi _{2}\oplus \left ( \chi _{1}\oplus \chi _{1} \right )=\left ( \chi _{2}\oplus \chi _{1} \right )\oplus \chi _{1}=b\oplus \chi _{1}

就是另一个解。

        当p\geqslant 3时,\bigoplus A可能不为0,也可能为0。比如A=\left [ 6,5,3 \right ],整体取二进制按位异或就是

110\oplus 101\oplus 011=0.所以当p\geqslant 3时需要对问题进行降阶拆解:

        continuing

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 01:14:02       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 01:14:02       102 阅读
  3. 在Django里面运行非项目文件

    2024-07-22 01:14:02       83 阅读
  4. Python语言-面向对象

    2024-07-22 01:14:02       92 阅读

热门阅读

  1. deploy gitlab through docker

    2024-07-22 01:14:02       29 阅读
  2. 嵌入式软件技术能力

    2024-07-22 01:14:02       24 阅读
  3. Mad MAD Sum-Codeforces Round 960 (Div. 2)

    2024-07-22 01:14:02       27 阅读
  4. js | Core

    js | Core

    2024-07-22 01:14:02      22 阅读
  5. 堆、栈和队列(数据结构)

    2024-07-22 01:14:02       31 阅读
  6. 关于Spring Boot IOC&DC,看这一篇就够了

    2024-07-22 01:14:02       23 阅读
  7. 关于数据库索引

    2024-07-22 01:14:02       28 阅读
  8. 【Node.js基础04】node.js模块化

    2024-07-22 01:14:02       24 阅读
  9. Postman实战案例:从零开始设计API测试流程

    2024-07-22 01:14:02       29 阅读