n-m 问题

前言

前几天写了一个文章 位运算 的探究,然后有人问假设大部分出现的数字都是4个相同，只有一个是2个相同怎么做，这个问题我们可以称为4-2问题。

也就是说告诉你N个数, 其中只有一个数出现m次, 其他的数都出现n次,则称为n-m问题。

首先n肯定不能等于m了，且两个数都是正整数了。

之后n和m的关系有两个： n>m 和 n<m.

基本做法

请参考 位运算 的探究 的基础做法。

2-m 问题

如果 m为1，这个就是大家最常见的问题，大部分数出现两次，只有一个出现1次，直接异或所有数字就得到答案了。

我们也可以套用原理来解释。

• 即默认 one 为0, 即任何数字都不存在
• 来一个数字a 后one标记这个数字a存在.
• 再来一个数字a后one标记这个数字a不存在.

按上面的分析转化为位操作的状态转移就是下表。

状态转移对应的公式就是

one = one^a;

如果m大于2呢？

如果m为奇数，还是可以转化为2-1问题的，即出现m%2次，但是如果是偶数就没办法解决了。

为什么呢？

假设b在前面的出现两次，b多次出现两次，加起来就是b出现2n次。

这样的话任何数都可以通过出现多次n次来到达m次，而我们是不能区分这个的。

有人说假设每个数字只会出现一个n次和一个m次不就行了嘛？

答案是不行的，因为我们我们会转化为微观位操作，这时就是统计0与1的个数了。

所以如果n是m的约数的话，我们只能采用上面的O(n log(n))基础做法了.

那如果不是约数会怎样呢，我们先继续向下看看就知道了。

3-m问题

假设m为1，就是上面的3-1问题，位运算 的探究 介绍的很清楚，下面我只把状态描述和公式一下吧。

• 默认one,two都是0, 即任何数字都不存在
• 数字a第一次来的时候, one标记a存在, two不变
• 数字a第二次来的时候, one标记a不存在, two标记a存在
• 数字a第三次来的时候, one不变, two标记a不存在

ones = (ones ^ a) & ~twos;
twos = (twos ^ b) & ~ones;

然后如果m为2呢，这个和3-1问题的状态有哪些不同呢？
好像没有影响，我们只需要还是用那个状态和公式，最后答案会在 two 中罢了。

那如果m为大于3的数字呢？
由于3是质数，m又不能是3的倍数，所以m 模 3 不能等于0。 此时我们可以把m看做出现 m/3 个3次a和出现一个m%3次a吧。

这样有转化为3-m (3>m) 的问题了。

n-m 问题猜想

这里我们是不是可以得到结论了呢？

如果m%n ==0 的话，没有O(n)做法，否则有，而且问题可以转化为 n-(m%n) 问题。

通用公式

假设m不是n的倍数，那么我们能不能找到一个通用公式呢？

实际上现在已经于m无关了。

由于最多出现n次，所以我们需要 log(n) + !!(n&(n-1)) 个数字来表示状态。

注：现在下面只是一些推导，没有得到通用公式。

比如4-3 问题，log(4) + !!(4&(4-1)) = 2.

其实3-1的标准做法应该是下面的做法。最后两个数字需要进行或运算.

ans = onw | two;

状态原理如下

• 默认one,two都是0, 即任何数字都不存在
• 数字a第一次来的时候, one标记a存在, two不变 (10)
• 数字a第二次来的时候, one标记a不存在, two标记a存在 (01)
• 数字a第三次来的时候, one标记a存在, two不变 (11)
• 数字a第四次来的时候, one标记a不存在, two标记a不存在 (00)

状态转移如下

那状态转移公式我们能不能得到呢？

我们打出一张很大很大的表

然后发现

one = a^one1;

假设 two2 是和 a\^two1 或 ~(a\^two1) 异或得到的，则异或的那个数字就需要是 01000100 或 10111011 了。

简洁的式子有下面几个

a & one1  = "00010001";
a | one1  = "01110111";
a & ~one1 = "01000100";
a | ~one1 = "11011101";
a & two1  = "00000101";
a | two1  = "01011111";
a & ~two1 = "01010000";
a | ~two1 = "11110101";
a & one2  = "01000100";
a | one2  = "11011101";
a & ~one2 = "00010001";
a | ~one2 = "11011101";

然后发现 a & ~one1 和 a & one2 都可以。

也就是

  a & ~one1
= a & one2
= a & (a^one1)
two = a ^ two1 ^ (a & one2)

再根据 位运算 的探究 里面的高级公式，我们就可以得到

two= two ^ (a & ~one2)

而整个n-m问题的通用公式，等周末我推导一下吧，读者如果自己推导出来了可以留言告诉我。