[TL]在大数组中找重复和丢失的整数

[Beyond]

偶然在网上看到这样一则问题，说是只要能说出解法，就通过了某公司面试第一关，与谷歌惯用的招聘方式有那边点相似，但非出自谷歌。招聘不招聘的，倒不感冒，个人觉得解决该问题还是有点意思的，有兴趣的兄弟大可说说高见。

问题描述：

给定一个long long型的大整数N，有N个整数组成的数组，数组中每个整数n：1<=n<=N，并且仅出现一次，其中只有一个n1是重复的，即出现了两次，而有一个整数n2不在数组中。求一种线性复杂度算法，能在较小不变的内存空间中，找到重复的整数n1和丢失的整数n2。

鄙人有种比较拙略的线性算法，如果大家对该topic有兴趣，随后交流。

[Ray Song]

全部 xor

2011/7/12 Beyond <beyo...@gmail.com>

[Ray Song]

我看错了

2011/7/12 Ray Song <emac...@gmail.com>

[Ray Song]

二分吧，求 m=floor((1+N)/2)，计算 1^2^3^...^m，m+1^m+2^...n 可以知道 n1 和 n2 是否在不同边或在同一边

2011/7/12 Ray Song <emac...@gmail.com>

[alai]

如果不考虑溢出和精度的话，全部加起来和1+2+...+N相比，得到n1-n2，全部乘起来和1*2*...*N相比，得到n1/n2，只要n1 != n2，就可以求出n1和n2。

[qiaojie]

int a[N] = {3,2,5,1,6,8,7,9,3,10};

int b[N];

int i;

for(i = 0; i < N; ++i)

b[i] = -1;

for(i = 0; i < N; ++i)

{

if(b[a[i] - 1] != -1)

printf("repeat number:%d\n", a[i]);

else

b[a[i] - 1] = a[i];

}

for(i = 0; i < N; ++i)

{

if(b[i] == -1)

printf("missing number: %d\n", i + 1);

}

2011/7/12 Beyond <beyo...@gmail.com>

[彭国兴]

麻烦问下，题意是不是这样的，有一个long long类型的变量N，有一个长度为N的数组，数组内的元素为从1到N，其中某一个元素出现了两次，某一个元素没有出现。

如果是这样的话，我想的是能不能这样。申请一个长度为N的内存空间，初始化为0，分别对应1~N，然后读取数组中的元素，每读取一个元素，做一次判断，如果此时相应内存空间内值为1，则该数据出现两次，否则将响应位赋1。数组读取完后，依次读取所申请的内存空间中的值，值为0的位对应于所申请内存空间的偏移量+1则为没有出现的数据。

[Wu Yin]

这个比较靠谱. 不过如果不允许动原数据的话, 我想不到怎么在O(n)的时间内搞定, 朴素实现显然是O(nlgn).

如果允许动原数据的话倒是可以每次类似quicksort来partition一下

另外回上面几楼， 明确要求空间不能过大了， 最起码得是o(N)的吧

2011/7/12 Ray Song <emac...@gmail.com>

--
滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。
----------

Xiamen University Cognitive Science Department, Brain-like Intelligent System Labs

Blog (all about mathematics & algorithms): http://wywcgs.wordpress.com
Email: wyw...@gmail.com
Gtalk: wyw...@gmail.com
MSN: wyw...@hotmail.com

QQ: 346693733

TopCoder Handle: wywcgs

[qiaojie]

刚才那个解法需要开辟新的内存空间，改进了一下，在原数据上做排序，就不需要另外开辟内存空间了

int a[N] = {3,2,5,1,6,8,7,9,5,10};

int repeatNum;

int i = 0;

while(i < N)

{

int n = a[i] - 1;

if(n == i)

i++;

else if(a[n] == a[i])

{

repeatNum = n + 1;

i++;

}

else

exchange(a[n], a[i]);

}

printf("repeat number: %d\n", repeatNum);

for(i = 0; i < N; ++i)

{

if(a[i] != i + 1)

printf("missing number: %d\n", i + 1);

}

很显然，交换次数一定小于N，所以是线性负载度

2011/7/12 qiaojie <qia...@gmail.com>

[Alecs King]

hint:

求和
求平方和
取差

易得 n1-n2 和 n1^2-n2^2 即得 n1+n2, n1, n2

--
Alecs King

[lzprgmr]

这个比较靠谱！

Blog: http://www.cnblogs.com/baiyanhuang/
Douban:http://www.douban.com/people/baiyanhuang/

2011/7/12 Alecs King <al...@perlchina.org>

[Zhiming G]

找两种运算列方程组, 这两种运算需要有可计算的求和公式和O(1)的一次计算时间就行, 然后列方程:

G(1..N) + g(n1, n2) = G(A[1]..A[N])

F(1..N) + f(n1, n2) = F(A[1]..A[N])

其中F,G是两种常见操作, g和f是依赖G和F的已知表达式.

比如 F 是加法, G是平方和.

确定F/G时需要考虑一下解方程是否可解, 求解复杂度, 计算精度, 数字表示范围等~

2011/7/12 Alecs King <al...@perlchina.org>

[Beyond]

恩   这确实是个解法，但是精度控制就会带来相当的复杂度，而且，内存也不能满足条件：需要在一个较小的不变的空间中求解。可以试想一下，从1到N相乘，能达到怎么样一个数量级，我很难想象。。。

在 2011年7月12日 下午10:48，alai <ala...@gmail.com>写道：

[Beyond]

这里面有一个条件，就是说，必须在一个不变的较小的内存中实现算法，而给定的N，可能很大，比如是18位长的整数，那么产生的数组所需的空间用“T”都存不下的，而原来的数组不一定存在内存中，这个是个隐含条件，在题中没有说明，是在下的失误。说的再直接点的话，就是，请考虑能在32位系统下运行，并线性求解。

[Beyond]

如果N很大时，那这块内存是非常之巨大的，不符合题中的一个条件。事实上，如果不考虑内存的话，这个问题就不值得讨论了。

[Beyond]

内存当然不能是O(N)，如果是这个数量级的内存，那么这题就非常简单了。请考虑能在32位系统下运行。然后是能动原数据，你所说的方法是不是线性先不考虑，你只考虑了分段处理，但是分段后的合并呢，分段处理后的数据的存储呢？这部分处理带来的复杂度呢？请仁兄再考虑。

[Shujie Shang]

二分异或可以

在 2011年7月12日 下午10:36，Ray Song <emac...@gmail.com> 写道：

[Beyond]

这个方法感觉比较靠谱，仁兄能把方法说的具体点吗？

在 2011年7月12日 下午10:36，Ray Song <emac...@gmail.com>写道：

[Wu Yin]

什么合并不合并的。那个方法根本不需要什么合并过程，你是没听明白那个方法啥意思吧。

假设数出现的区间是[a, b]，把这些数分成两部分，一部分是数值在[a, (a+b)/2)的数，一部分是[(a+b)/2, b)的数。如果这两部分每个数正好出现一次，那么它们XOR之后的“和“都可以算出来。然后我们在数组中统计所有在这两个区间内数XOR的结果，顺便统计一下数的个数。

如果和相应部分正常情况（就是每个数正好出现一次）相同（包括XOR sum和个数），那么代表这段区间没问题，问题出现在另一半区间。如果不一样，那么代表这段区间有问题，那你根据统计出来的个数可以判断出到底出了什么问题（多了一个还是少了一个）。每个都分别可以很简单的做出来。

总共需要跑的趟数，每次长度变为一半，需要O(lgn)次，总复杂度O(nlgn)。

另外，上面那个求n1-n2和n1^2-n2^2也能在32位系统下做吧？无非就是写个biginteger而已，需要的精度高不了多少。

2011/7/13 Beyond <beyo...@gmail.com>

[OxFAN]

高精度不会写么? long long型最多64位二进制位,N!最多就是个几百位二进制位的数,具体位数可以用斯特林公式求得,1KB空间储存这个数绰绰有余,何来的内存问题?

2011/7/13 Beyond <beyo...@gmail.com>

[Beyond]

你怎么保证你所取的数据区间排序之后一定是连续的整数呢？

[Wu Yin]

你搞错了吧。

用stirling's formula代入一下10^9（都不用带入10^18），然后再求一个log，你看看到底有多少位？

20!就已经超越long long表示的上限了，何况10^9

2011/7/13 OxFAN <oday...@gmail.com>

[Wu Yin]

我的方法理有提到排序么

2011/7/13 Beyond <beyo...@gmail.com>

[Beyond]

我觉得你可以试一下

[OxFAN]

N!的计算可以用高精度阿,没说这结果必须要在long long范围内吧.

2011/7/13 Wu Yin <wyw...@gmail.com>

[OxFAN]

好吧,确实搞错了..

2011/7/13 OxFAN <oday...@gmail.com>

[Wu Yin]

我是说20!就已经超越long long了，你可以想象一下n!增长的速度到底有多快

事实上log(n!) = O(nlgn)没有问题吧，也就是说你需要的内存起码是O(nlgn)这么多

还不如O(n)空间的counting sort呢

2011/7/13 OxFAN <oday...@gmail.com>

[OxFAN]

其实也可以用 a1/1 * a2/2 * a3/3 .... an/n,an是输入的数列,为避免精度损失,an/n可以用分数表示,储存约分后的结果,不转换成小数.

2011/7/13 OxFAN <oday...@gmail.com>

[qiaojie]

如果数组不在内存里，一样可以用这个算法搞定，只要你这个数据结构可以读写可以随机访问就行了，我的解法不需要额外的存储空间，复杂度也是O(n)，我不认为有不满足题目要求的地方。

 

2011/7/13 Beyond <beyo...@gmail.com>

[Navi]

我觉得朴素就是O(n*log(MAX_LONG_LONG))吧... 把64这个常数忽略掉了就是O(n)...
假设这两个数是x和y
XOR(a[i] ^ i | i from 1 to N) = x ^ y
然后从高位开始一位一位搞，设P = {1 .. N}。假设搞到第j位，如果两个数第j位是一样的那么就通过比较XOR(a[i] ^ i | i属于P且(i & 1ULL << j) != 0)是否=0来确定这两个数在第j位的值，然后通过这一位是1还是0从P中筛掉不满足的得到新的P。
如果两个数在第j位是不同的，那么把P中的数按i & 1ULL << j分成两类，分开做一遍就好了。

2011/7/12 Wu Yin <wyw...@gmail.com>

--
Sincerely,

Junyuan Zhuang (Navi)

Email: nav...@gmail.com
Twitter: http://twitter.com/navimoe
Facebook: http://www.facebook.com/navi.amoy

[Beyond]

这个是题目的出处：http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/#comment-391 ， 大家有兴趣可以把想法发送到上面去

[qiaojie]

好吧，原题是说：your algorithm should run in small constant space and leave the array untouched，而你没说数组不能改。

前面有人说了，用n1 -  n2, n1*n1 - n2*n2就可以解出。另外，用n1-n2和n1^n2也可以解出来

2011/7/13 Beyond <beyo...@gmail.com>

[Roy Lee]

把数组中所有元素和1到N异或一遍，得到的结果是n1^n2,且它肯定不是0，选取其中不为0的任一bit，根据其是否为0可以将数组元素划分为两组，当然也可以把1到N划分为两组，n1n2分别在这两组中，，接下来不用说了吧

[Xinyu LIU]

Hi,

赞一个！

另： 具体实现时不用sum(xs)-sum([1..n])
可以：

let
  m =sum $ map (\(a, b)-> a-b) $ zip xs [1..]
  n = sum $ map(\(a, b)-> a*a - b*b) $ zip xs [1..]
in
  x = (m+n/m) / 2
  y = (n/m-m) / 2

另外存在另外一个min-free类似的解法，但是要求in-place变化array：

开会去了，回头写...

2011/7/12 Alecs King <al...@perlchina.org>

--
--
Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY

[Wang Feng]

为什么不用 bitmap 呢? 既然这么大的数组都出来了, bitmap 用的内存不过是这个数组的六十四分之一而已,没有道理不可以用的。

[OxFAN]

bitmap超内存了.. 前面LZ说是32位机器

求和和乘积的貌似不行,即使用a1/1 * a2/2 ... * an/n 虽然可以约分,但也可以通过精心设计的an导致溢出(将素数都排在前面).

现在看那个计算平方和的方法比较好一些

2011/7/13 Wang Feng <wanng...@gmail.com>

[Alecs King]

On Tue, Jul 12, 2011 at 11:23:28PM +0800, Alecs King wrote:
> On Tue, Jul 12, 2011 at 09:33:15PM +0800, Beyond wrote:
> > 偶然在网上看到这样一则问题，说是只要能说出解法，就通过了某公司面试第一关，与谷歌惯用的招聘方式有那边点相似，但非出自谷歌。招聘不招聘的，倒不感冒，个人觉得解决该问题还是有点意思的，有兴趣的兄弟大可说说高见。
> >
> > 问题描述：
> > 给定一个long
> > long型的大整数N，有N个整数组成的数组，数组中每个整数n：1<=n<=N，并且仅出现一次，其中只有一个n1是重复的，即出现了两次，而有一个整数n2不在数组中。求一种线性复杂度算法，能在较小不变的内存空间中，找到重复的整数n1和丢失的整数n2。
> >
> > 鄙人有种比较拙略的线性算法，如果大家对该topic有兴趣，随后交流。
>
> hint:
>
> 求和
> 求平方和
> 取差
>
> 易得 n1-n2 和 n1^2-n2^2 即得 n1+n2, n1, n2

Show me code! show me THE code!! show me MORE code!!!

------------------------------8<--------------------------------
#!/usr/bin/python

# please note that all numbers are processed sequentially.
# the following code stores all the original numbers in an array
# just for convenience of demo.

# sum method: one pass
# time O(n), space O(1)
# return (dup, miss)
def get1(n, a):
s = n*(n+1)/2
sq = n*(n+1)*(2*n+1)/6
for x in a:
s -= x
sq -= x*x
sq /= s
return (sq-s)/2, (sq+s)/2

# xor method: two pass
# time O(n), space O(1)
# return (dup, miss)
def get2(n, a):
s = 0
for x in xrange(n):
s ^= (x + 1) ^ a[x]
bit = 1
while (s & bit) == 0:
bit <<= 1
c1, c2 = 0, 0
x1, x2 = 0, 0
for x in xrange(n):
if a[x] & bit:
x1 ^= a[x]
c1 += 1
else:
x2 ^= a[x]
c2 += 1
if (x+1) & bit:
x1 ^= (x+1)
c1 -= 1
else:
x2 ^= (x+1)
c2 -= 1
if c1 == 1:
return x1, x2
else:
return x2, x1

# the stupid, fat but obviously correct method
# for checking answers
# time O(n), space O(n)
# return (dup, miss)
def get3(n, a):
hit = [0] * (n+1)
d, m = 0, 0
for x in a:
if hit[x]:
d = x
hit[x] += 1
for x in xrange(1, n + 1):
if hit[x] == 0:
m = x
break
return d, m

# quick & dirty tests
import random
r = random.Random()
def test():
n = r.randint(2, 10000)
a = range(1, n+1)
while True:
x, y = r.randint(1,n), r.randint(1,n)
if x != y:
a[x-1] = y
break
r.shuffle(a)
print get1(n, a) == get2(n, a) == get3(n, a)

print get1(5, [1,1,3,4,5])
print get2(5, [1,1,3,4,5])
print get3(5, [1,1,3,4,5])
for x in xrange(100):
test()
------------------------------>8--------------------------------

--
Alecs King

[Alecs King]

On Wed, Jul 13, 2011 at 10:39:18AM +0800, Wu Yin wrote:
> 什么合并不合并的。那个方法根本不需要什么合并过程，你是没听明白那个方法啥意思吧。
> 假设数出现的区间是[a, b]，把这些数分成两部分，一部分是数值在[a, (a+b)/2)的数，一部分是[(a+b)/2,
> b)的数。如果这两部分每个数正好出现一次，那么它们XOR之后的“和“都可以算出来。然后我们在数组中统计所有在这两个区间内数XOR的结果，顺便统计一下数的个数。
> 如果和相应部分正常情况（就是每个数正好出现一次）相同（包括XOR
> sum和个数），那么代表这段区间没问题，问题出现在另一半区间。如果不一样，那么代表这段区间有问题，那你根据统计出来的个数可以判断出到底出了什么问题（多了一个还是少了一个）。每个都分别可以很简单的做出来。
> 总共需要跑的趟数，每次长度变为一半，需要O(lgn)次，总复杂度O(nlgn)。
>

利用统计xor sum和个数的这个思路，不必二分。 :)
直接 xor 出来，随便找出1位划分。然后再跑一趟，分别 xor/计数即可。
python^W^W^W^W^Wseudo code 见另一封邮件。

--
Alecs King

[Alecs King]

On Wed, Jul 13, 2011 at 12:46:28PM +0800, qiaojie wrote:
> 另外，用n1-n2和n1^n2也可以解出来

仅靠这两个数值是解不出的。

比如 n1, n2 二进制表示只差一位的情况下:

n1 = abcdefg1xyz
n2 = abcdefg0xyz

abcdefgxyz 可为任意数值

--
Alecs King

[Ray Song]

嗯，计算 a[0]^a[1]^...^a[n-1] ^ 1^2^...^n = n1^n2 可以知道 n1、n2 的哪一个二进制位不同，把这位为0的数的个数和 xor 求出来，把这位为1的数的个数和 xor 求出来，就能知道 n1 n2

2011/7/13 Alecs King <al...@perlchina.org>

[Alecs King]

On Wed, Jul 13, 2011 at 05:58:41PM +0800, Alecs King wrote:
> python^W^W^W^W^Wseudo code 见另一封邮件。

s/W/H/g

--
Alecs King

[Xinyu LIU]

Hi,

刚刚有空，前面的没有细看，看我这个O(N)的解法：

#!/usr/bin/python

import random

# [l, u)

def solve(xs):

    l = 0

    u = len(xs)

    while l<u:

        m = (l+u)/2

        left = [x for x in xs if x < m]

        right = [x for x in xs if x >= m]

        if len(left) < m - l:

            lost = (m - 1 + l)*(m - l)/2 - sum(left)

            dup  = sum(right) - (u - 1 + m)*(u - m)/2

            return (lost, dup)

        elif len(left) > m - l:

            lost = (u - 1 + m)*(u - m)/2 - sum(right)

            dup  = sum(left) - (m - 1 + l)*(m - l)/2

            return (lost, dup)

        else:

            if sum(left) == (m -1 + l)*(m - l)/2:

                l = m

                xs = right

            else:

                u = m

                xs = left

# quick and dirty test.

def test():

    for i in range(100):

        n = random.randint(0, 10000)

        xs = range(n)

        lost = random.choice(xs)

        xs.remove(lost)

        dup = random.choice(xs)

        xs.append(dup)

        random.shuffle(xs)

        assert(solve(xs) == (lost, dup))

    

if __name__=="__main__":

    test()

2011/7/13 Alecs King <al...@perlchina.org>

[wujin chen]

没看全上面的回复，我也来贡献个简洁有力的O(n)解法吧，不用额外的空间，除了几个变量，扫描一遍即得到重复的数字和丢失的数字。
大体的思路就是冲突检测~~代码里的数组不用0位了，从1开始存储数据，处理起来比较方面。

见代码：
public class FindDuplicateAndLost {
    public void find(int[] a){
        int duplicated = -1;
        int lost = -1;
        for(int i = 1; i < a.length; i++){
            while(a[i] != i){
                if(a[i] == a[a[i]]){
                    duplicated = a[i];
                    lost = i;
                    break;
                }else{
                    int temp = a[i];
                    a[i] = a[a[i]];
                    a[temp] = temp;
                }
            }
        }
        System.out.printf("%d duplicated, %d lost.", duplicated, lost);
    }
   
    public static void main(String[] args) {
        FindDuplicateAndLost test = new FindDuplicateAndLost();
        int[] a  = {-1,4,2,3,4,5,6,7,8,9,10};//{-1,3,7,4,3,1,8,2,5,9};
        test.find(a);
    }
}  
PS.谁有实习机会可否推荐下~~？研二，想边实际锻炼边学习

[Xinyu LIU]

说一下为什么我的解法是O(N)的。

令：l为lower bound, u为upper bound

我们用左闭右开区间 [l, u)代表带差区间。

算法先取中间位置, m = (l + u)/2作为pivot，将序列一分为二，左侧为所有小于m的元素，右侧为所有大于m的元素。

  - 若左侧元素个数少于一半，则丢失的元素在左侧，重复的元素在右侧，用等差数列(l, l+1, ...m-1)和减去左侧元素和即得到丢失的元素，用右侧元素和减去等差数列(m, m+1, ..., u-1)的到重复元素；

  - 若左侧元素个数多余一半，则重复元素在左侧，丢失元素在右侧，同样用等差数列和的方法可得到答案

  - 若左侧元素个数恰好等于一半，且左侧元素和恰好等于等差数列和，则丢弃左侧，重复d&c在右侧寻找答案；否则丢弃右侧，在左侧继续找答案。

复杂度分析：

  一分为二使用类似quick sort的partition算法，复杂度为O(N)，若不允许in place改变数组，则需要构造两个一半长度的数组；

  等差数列求和利用通项公式为O(1)，左侧，右侧序列求和复杂度为O(N)

  统计左右序列个数最差为O(N)

  故算法性能表示为 T(N) = 2T(N/2) + O(N)

得复杂度为O(N)，故我的算法为线性复杂度。

2011/7/13 Xinyu LIU <liuxi...@gmail.com>

[Xinyu LIU]

2011/7/13 Xinyu LIU <liuxi...@gmail.com>

[Xinyu LIU]

Hi,

严重错误：故算法性能表示为 T(N) = T(N/2) + O(N)

也就是说，O(N + N/2 + N/4 + ... ) = O(2N) = O(N)

每次干掉一半，D&C

非常抱歉前面还发了个空mail.

2011/7/13 Xinyu LIU <liuxi...@gmail.com>

[zhangyingneng]

说这个 T(N) = T(N/2) + O(N)  是 O(N) 的算法也挺吭爹的.

2011/7/13 Xinyu LIU <liuxi...@gmail.com>

Hi,

[lzprgmr]

这个怎么求出来？

假设是1 2 3 4 4 6

n1 = 4, n2 = 5

利用LST位不同分成两组：

1 3

2 4 4 6

没看出来能求出n1, n2

Blog: http://www.cnblogs.com/baiyanhuang/
Douban:http://www.douban.com/people/baiyanhuang/

2011/7/13 Ray Song <emac...@gmail.com>

[Xinyu LIU]

Hi,

抱歉我对新词不大懂。

类似算法可以参见Richard Bird. "Pearls of functional algorithm design". Cambridge University Press; 1 edition (November 1, 2010), Chapter 1。

以及：https://sites.google.com/site/algoxy/introduction （要穿墙）

2011/7/13 zhangyingneng <zhangy...@gmail.com>

[Eric Miao]

T(N) = T(N/2) + O(N)  是 O(N)  ?  还是 O(NlgN)

2011/7/14 Xinyu LIU <liuxi...@gmail.com>

[Zhiming G]

(1^3) ^ (1^3^5) = 5

#(1, 3) = 2 < #(1, 3, 5)

so, n2 = 5

(2^4^4^6) ^ (2^4^6) = 4

#(2, 4, 4, 6) = 4 > #(2, 4, 6)

so, n1=4

2011/7/14 lzprgmr <baiya...@gmail.com>

[Xinyu LIU]

第一次扫描并处理全序列O(N)
干掉一半后，第二次只需要扫描并处理O(N/2)
再干掉一半后，第三次只需扫描并处理O(N/4)
...
等比数列求和：O(N+N/2+N/4+...) = O(2N) = O(N)

经典的D&C, 有什么问题么？

请注意这里和quick sort which is O(N \lg N)的区别，quick sort每次处理O(N)，总共期望次数为O(\lg N)，故而其复杂度为O(N \lg N)；
而此算法每次处理O(N/2^i)，次数为O(\lg N)， 故总复杂度为O(N)。

PS: 你有仔细看我给的link reference么？

2011/7/14 Eric Miao <eric....@gmail.com>

[Ray Song]

二分xor是这样的，候选数范围最坏情况下每次缩小一半（最好情况下 n1 n2 落在不同区域，统计每个区域的个数 和 xor 就能确定 n1 n2）

但是因为原数组不能改动，每次需要 O(n) 扫描整个数组得知 [a,b) 间的数的个数

O(n)+O(n)+...+O(n)(一共 O(log n) 个) = O(n log n)

2011/7/14 Xinyu LIU <liuxi...@gmail.com>

[Ray Song]

抱歉，前面忘记看你的代码了，你的时空复杂度均 O(n)
二分 xor 如果每次扫描整个数组，时 O(n log n)，空 O(1)
还有种求出 n1 ^ n2 后选择一个 n1 n2 差异二进制位对原数组分类，时 O(n)，空 O(1)

2011/7/14 Xinyu LIU <liuxi...@gmail.com>

[Xinyu LIU]

Hi,

如果允许in-place partition，我的空间复杂度是O(1)
below is the updated code which use in-place partition:

def partition(xs, l, u, x):
    left = l
    for right in range(l, u):
        if xs[right] < x:
            (xs[left], xs[right]) = (xs[right], xs[left])
            left = left + 1
    return left

def solve_inplace(xs):
    (l, u) = (0, len(xs))

    while l<u:
        m = (l+u)/2

        m1 = partition(xs, l, u, m)
        (nl, nr) = (m1 - l, u - m1);
        (sl, sr) = (sum(xs[l:m1]), sum(xs[m1:u]))
        sl1 = (l + m - 1)*(m - l)/2
        sr1 = (m + u - 1)*(u - m)/2
        if m1 < m:
            return (sl1 - sl, sr - sr1)
        elif m1 > m:
            return (sr1 - sr, sl - sl1)
        else:
            if sl == sl1:
                l = m1
            else:
                u = m1

测试：
def test_solve_inplace():

    for i in range(100):
        n = random.randint(0, 10000)
        xs = range(n)
        lost = random.choice(xs)
        xs.remove(lost)
        dup = random.choice(xs)
        xs.append(dup)
        random.shuffle(xs)

        assert(solve_inplace(xs) == (lost, dup))

2011/7/14 Ray Song <emac...@gmail.com>

[Xinyu LIU]

Hi,

此程序找duplicate没有问题，但是找lost会有bug:
反例如下(我用从0开始的index)：
xs  = [5，0，1，3，2，5]

进入循环后，发现xs[0]不是0，而是5，于是进而检查xs[5]，发现正好是5，于是得到duplicate为5，但是lost并非0，而是4。

2011/7/13 wujin chen <wujinc...@gmail.com>

[Mikster.Z]

贵公司一定很清闲。

[Ray Song]

如果允许修改的话，
for i in [0..n-1] do swap(a[a[i]], a[i]) end
最方便了

[gzc9047]

a[1]+...+a[N] - (1+...+N) = n1-n2 = M1
a[1]^2+...+a[N]^2 - (1^2+...+N^2) = n1^2-n2^2 = M2
M1/M2 = n1+n2
就这样咯。

On 7月12日, 下午9时33分, Beyond <beyond...@gmail.com> wrote:
> 偶然在网上看到这样一则问题，说是只要能说出解法，就通过了某公司面试第一关，与谷歌惯用的招聘方式有那边点相似，但非出自谷歌。招聘不招聘的，倒不感冒，个人 觉得解决该问题还是有点意思的，有兴趣的兄弟大可说说高见。
>
> 问题描述：
> 给定一个long
> long型的大整数N，有N个整数组成的数组，数组中每个整数n：1<=n<=N，并且仅出现一次，其中只有一个n1是重复的，即出现了两次，而有一个整数n2 不在数组中。求一种线性复杂度算法，能在较小不变的内存空间中，找到重复的整数n1和丢失的整数n2。
>
> 鄙人有种比较拙略的线性算法，如果大家对该topic有兴趣，随后交流。

[raymond]

我将大家的想法做了一个简单的总结，欢迎批评指正。
http://www.cnblogs.com/raymondshiquan/archive/2011/07/16/2108150.html

On Jul 13, 12:30 am, Zhiming G <gaoz...@gmail.com> wrote:
> 找两种运算列方程组, 这两种运算需要有可计算的求和公式和O(1)的一次计算时间就行, 然后列方程:
>
> G(1..N) + g(n1, n2) = G(A[1]..A[N])
> F(1..N) + f(n1, n2) = F(A[1]..A[N])
>
> 其中F,G是两种常见操作, g和f是依赖G和F的已知表达式.
> 比如 F 是加法, G是平方和.
>
> 确定F/G时需要考虑一下解方程是否可解, 求解复杂度, 计算精度, 数字表示范围等~
>
> 2011/7/12 Alecs King <al...@perlchina.org>
>
>
>
>
>
>
>
> > On Tue, Jul 12, 2011 at 09:33:15PM +0800, Beyond wrote:
>
> > 偶然在网上看到这样一则问题，说是只要能说出解法，就通过了某公司面试第一关，与谷歌惯用的招聘方式有那边点相似，但非出自谷歌。招聘不招聘的，倒不感冒，个人觉得解决该问题还是有点意思的，有兴趣的兄弟大可说说高见。
>
> > > 问题描述：
> > > 给定一个long
>
> > long型的大整数N，有N个整数组成的数组，数组中每个整数n：1<=n<=N，并且仅出现一次，其中只有一个n1是重复的，即出现了两次，而有一个整数n2不在数组中。求一种线性复杂度算法，能在较小不变的内存空间中，找到重复的整数n1和丢失的整数n2。
>
> > > 鄙人有种比较拙略的线性算法，如果大家对该topic有兴趣，随后交流。
>

> > hint:
>
> > 求和
> > 求平方和
> > 取差
>
> > 易得 n1-n2 和 n1^2-n2^2 即得 n1+n2, n1, n2
>

> > --
> > Alecs King

[Xinyu LIU]

Hi,

Sorry, My fault，conflict后是break, 不是return，原程序没有问题。

2011/7/14 Xinyu LIU <liuxi...@gmail.com>

[error right]

a1 +..an -x + y = 1+....n

C^x^y             = 1^2^3^4^...^n

-->

y -x = B

C^x^y = D

-->

C^x^y - C^x= C^x^B
C^x^y = D

C^x + C^x^B =  D

最多再 for 循环一次,不就行了....推理是不是错了.

2011/7/18 Xinyu LIU <liuxi...@gmail.com>

[error right]

有问题,未比有維一解

2011/9/23 error right <error...@gmail.com>

[heart]

先排序，后遍历。就是nlgn复杂度

On Sep 23, 9:51 am, error right <error.ri...@gmail.com> wrote:
> 有问题,未比有維一解
>
> 2011/9/23 error right <error.ri...@gmail.com>> a1 +..an -x + y = 1+....n

> > C^x^y = 1^2^3^4^...^n
>
> > -->
> > y -x = B
> > C^x^y = D
>
> > -->
> > C^x^y - C^x= C^x^B
> > C^x^y = D
> > C^x + C^x^B = D
>
> > 最多再 for 循环一次,不就行了....推理是不是错了.
>

> > 2011/7/18 Xinyu LIU <liuxiny...@gmail.com>

>
> >> Hi,
>
> >> Sorry, My fault，conflict后是break, 不是return，原程序没有问题。
>

> >> 2011/7/14 Xinyu LIU <liuxiny...@gmail.com>

>
> >>> Hi,
>
> >>> 此程序找duplicate没有问题，但是找lost会有bug:
> >>> 反例如下(我用从0开始的index)：
> >>> xs = [5，0，1，3，2，5]
>
> >>> 进入循环后，发现xs[0]不是0，而是5，于是进而检查xs[5]，发现正好是5，于是得到duplicate为5，但是lost并非0，而是4。
>

> >>> 2011/7/13 wujin chen <wujinchen...@gmail.com>

>
> >>>> 没看全上面的回复，我也来贡献个简洁有力的O(n)解法吧，不用额外的空间，除了几个变量，扫描一遍即得到重复的数字和丢失的数字。
> >>>> 大体的思路就是冲突检测~~代码里的数组不用0位了，从1开始存储数据，处理起来比较方面。
>
> >>>> 见代码：
> >>>> public class FindDuplicateAndLost {
> >>>> public void find(int[] a){
> >>>> int duplicated = -1;
> >>>> int lost = -1;
> >>>> for(int i = 1; i < a.length; i++){
> >>>> while(a[i] != i){
> >>>> if(a[i] == a[a[i]]){
> >>>> duplicated = a[i];
> >>>> lost = i;
> >>>> break;
> >>>> }else{
> >>>> int temp = a[i];
> >>>> a[i] = a[a[i]];
> >>>> a[temp] = temp;
> >>>> }
> >>>> }
> >>>> }
> >>>> System.out.printf("%d duplicated, %d lost.", duplicated, lost);
> >>>> }
>
> >>>> public static void main(String[] args) {
> >>>> FindDuplicateAndLost test = new FindDuplicateAndLost();
> >>>> int[] a = {-1,4,2,3,4,5,6,7,8,9,10};//{-1,3,7,4,3,1,8,2,5,9};
> >>>> test.find(a);
> >>>> }
> >>>> }
> >>>> PS.谁有实习机会可否推荐下~~？研二，想边实际锻炼边学习
>