寻找特定数字问题
in 算法 with 0 comment

寻找特定数字问题

in 算法 with 0 comment

0x00 问题描述

给定一个整数数组,除了一个元素出现$p$次($p> = 1$,$p%k!= 0$),其余每个元素出现$k$($k>1$)次,找到那个特殊的元素。

0x01 含有1bit数字的特殊情况

假设我们有一个只包含1bit数字的数组(只能是$0$或$1$),我们想计算数组中$1$的数量,我们需要一个计数器count。这样每当数字$1$的数量count达到某个值时,比如说$k$, count返回$0$并重新开始。假设计数器具有二进制形式的$m$位:$x_m,...,x_1$(从最高有效位到最低有效位)。我们可以得出以下四个性质:

关键问题就在于:计数器中的每个位($x_1...x_m$)在扫描数组时如何变化。为了满足第二个性质,如果另一个操作数为$0$的话,我们使用哪些位运算会不改变操作数呢?$x = x | 0$和$x = x \oplus 0$。

好的,我们现在有两个可用的表达式:$x = x | i$或$x = x \oplus i$,其中$i$是输入数组中的元素。哪一个更好?我们还不知道,所以我们要实际操作一下。

开始时,计数器的所有位都初始化为零,即$x_m = 0,...,x_1 = 0$,保证计数器的所有位保持不变。如果我们碰到$0$,计数器将为$0$,直到我们碰到输入数组中的第一个$1$。在我们碰到第一个$1$之后,我们得到:$x_m = 0,...,x_2 = 0,x_1 = 1$。让我们继续,直到我们碰到第二个$1$,之后我们得到:$x_m = 0,...,x_2 = 1,x_1 = 0$,注意$x_1$从$1$变为$0$。如果使用$x_1 = x_1 | i$的话,在第二次计数之后,$x_1$仍然是$1$,所以很明显我们应该使用$x_1 = x_1 \oplus i$。 $x_2,...,x_m$呢?以$x_2$为例,如果我们此时碰到$1$并需要更改$x_2$的值,那么在我们进行更改之前,$x_1$的值必须是多少?答案是:$x_1$必须为$1$,否则我们不应该更改$x_2$,因为将$x_1$从$0$更改为$1$即可。因此,只有当$x_1$和$i$都是$1$时,$x_2$才会改变值,或者用数学公式表示为$x_2 = x_2 \oplus (x_1&i)$。类似地,只有当$x_{m-1},...,x_1$和$i$都是$1$:$x_m = x_m \oplus(x_{m-1}&...&x_1&i)$时,$x_m$才会改变值。

但是,你可能注意到上面的位运算结果范围是$0\sim 2 ^ m - 1$,而不是$k$。如果$k <2 ^ m - 1$,我们需要一些“分割”机制,当计数达到$k$时,将计数器重新初始化为$0$。为此,我们使用称为掩码的一些变量对$x_m,...,x_1$进行按位与,即$x_m = x_m&mask,...,x_1 = x_1&mask$。如果我们可以确保只有当计数达到$k$时掩码才为$0$并且对于所有其他计数情况都是$1$,那么我们就完成了我们的目标。我们如何实现这一目标?对于每个计数,我们对计数器的每个位都有唯一的值,可以将其视为其状态。如果我们用二进制形式写$k:k_m,...,k_1$,我们可以按如下方式构造掩码:

$mask =\sim (y_1&y_2&...&y_m)$,如果$k_j = 1$,$y_j = x_j$,如果$k_j = 0$,$y_j =\sim x_j$$(j = 1sim m)$。

我们举一些例子:

$k = 3:k_1 = 1,k_2 = 1,mask =\sim (x_1&x_2)$;

$k = 5:k_1 = 1,k_2 = 0,k_3 = 1,mask =\sim(x_1&\sim x_2&x_3)$;

总之,我们的算法将是这样的(nums是输入数组):

for(int i : nums){
    xm ^= (xm-1&...&x1&i);
    xm-1 ^= (xm-2&...&x1&i);
    .....
    x1 ^= i;
    mask = ~(y1&y2&...&ym) where yj = xj if kj = 1, and yj = ~xj if kj = 0
    xm &= mask;
    ......
    x1 &= mask;
}

0x02 具有32bit数字的一般情况

现在是时候将我们的结果从$1$位数的情况推广到$32$位整数。一种直接的方法是为整数中的每个位创建$32$个计数器。但是,如果我们利用位运算,我们可以“整体”管理所有$32$个计数器。通常说的“整体”,是指使用$m$个$32$位整数而不是$32$个$m$位计数器,其中$m$是满足$m> = logk$的最小整数,原因是位运算仅适用于每个位,因此不同位上的操作彼此独立(明显,对吧?)。这允许我们将$32$个计数器的相应位分组为一个$32$位整数。 下面的示意图展示如何完成操作

顶行是$32$位整数,对于每个位,我们有一个相应的$m$位计数器(由向上箭头下方的列显示)。由于$32$位中的每一位的逐位运算彼此独立,因此我们可以将所有计数器的第$m$位分组为一个$32$位数字(由橙色框显示)。此$32$位数字中的所有位(表示为$x_m$)将遵循相同的按位运算。由于每个计数器都有$m$位,我们最终得到$m$个$32$位数,它们对应于0x01中定义的$x_1,...,x_m$,但现在它们是$32$位整数而不是$1$位数。因此,在上面的算法中,我们只需要将$x_1$到$x_m$视为$32$位整数而不是$1$位数。其他一切都是一样的,我们就完成了。

0x03 返回什么

最后一件事是我们应该返回什么值,或者等价于$x_1$到$x_m$中的哪一个将等于Single Number。为了得到正确的答案,我们需要了解$m$个$32$位整数$x_1$到$x_m$的含义。以$x_1$为例, $x_1$有$32$位,我们将它们标记为$r(r = 1\sim 32)$。在我们完成扫描输入数组之后,$x_1$的第$r$位的值将由数组中所有元素的第$r$位确定(更具体地说,假设数组中所有元素的第$r$位为$1$的总计数是$q$,$q'= q%k$及其二进制形式:$q'_m,...,q'_1$,那么根据定义,$x_1$的第$r$位将等于$q '_1$)。现在你可以问自己这个问题:如果$x_1$的第$r$位是$1$,它意味着什么?

答案是找到可以为此做出贡献的$1$。出现$k$次的元素会有贡献吗?为什么没有?因为对于要贡献的元素,它必须同时满足至少两个条件:该元素的第$r$位是$1$并且该$1$的出现次数不是$k$的整数倍。第一个条件是微不足道的。第二个来自这样的事实:每当$1$的数量为$k$时,计数器将返回到零,这意味着$x_1$中的相应位将被重置为0。对于出现$k$次的元素,不可能同时满足这两个条件,所以它不会有所贡献。最后,只有出现$p(p%k \neq 0)$次的Single Number会有所贡献。如果$p> k$,那么第$k * \lfloor p / k\rfloor$Single Number不会有贡献。所以我们总是可以设置$p'= p%k$,并说Single Number出现$p'$次。

让我们以二进制形式写$p':p'_m,...,p'_1$(注意$p'<k$,所以它将适合$m$位)。这里我声称$x_j$等于Single Number的条件是$p'_j = 1(j = 1\sim m)$,下面给出一个简短的证明。

如果$x_j$的第$r$位为1,我们可以有把握地说Single Number的第$r$位也是$1$(否则没有任何东西可以使$x_j$的第$r$位为$1$)。我们要证明,如果$x_j$的第$r$位为$0$,那么Single Number的第$r$位只能为$0$。假设在这种情况下Single Number的第$r$位是$1$,让我们看看会发生什么。在扫描结束时,此$1$将被计为$p'$次。根据定义,$x_j$的第$r$位将等于$p'_j$,即1。这与$x_j$的第$r$位为0的假设相矛盾。因此,我们得出结论$x_j$的第$r$位将始终为与$p'_j = 1$时的Single Number的第$r$位相同。因为对于$x_j$中的所有位都是如此(即对于$r = 1\sim 32$为真),所以我们得出结论$x_j$将等于Single Number只要$p'_j = 1$。

所以现在很清楚我们应该返回什么。只需以二进制形式表示$p'= p%k$并且当$p'_j = 1$时返回相应的$x_j$即可。总的来说,算法是$O(n * logk)$时间和$O(logk)$空间复杂度。

附注:有一个将$x_j$到$p'_j$的每个位和Single Number $s$的每个位相关联的通用公式,$(x_j)_r = s_r&p'_j$,其中$(x_j)_r$和$s_r$分别表示$x_j$的第$r$位和$s$。从该公式可以很容易地看出,如果$p'_j = 1$,则$(x_j)_r = s_r$,即$x_j = s$。此外,如果$p'_j = 0$,我们有$(x_j)_r = 0$,即$x_j = 0$。所以我们得到这样的结论:如果$p'_j = 1$,$x_j = s$,如果$p'_j = 0$,则$x_j = 0$。这意味着表达式$(x_1 | x_2 | ... | x_m)$也将被计算为$s$,因为上述表达式中只包含$s$和一些$0$的or运算。

0x04 一些例子

以下是一些示例,用于说明算法的工作原理:

  public int singleNumber(int [] nums){
  int x1 = 0;
  for (int i : nums){
      x1 ^= i;
  }
  return x1;
  }
  public int singleNumber(int [] nums){
  int x1 = 0,x2 = 0,mask = 0;
  for (int i:nums){
      x2 ^= x1&i;
      x1 ^= i;
      mask = ~(x1&x2);
      x2 &= mask;
      x1 &= mask;
  }
  return x1; 
  }
  public int singleNumber(int [] nums){
  int x1 = 0,x2 = 0,x3 = 0,mask = 0;
  for (int i : nums){
      x3 ^= x2&x1&i;
      x2 ^= x1&i;
      x1 ^= i;
      mask = ~(x1&~x2&x3);
      x3 &= mask;
      x2 &= mask;
      x1 &= mask;
  }
  return x1;
  }

reference:

https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses