c*********t
发帖数: 2921 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: cookiesweet (apple), 信区: JobHunting
标 题: 关于那个经典的missing number的题
发信站: BBS 未名空间站 (Tue Jun 28 03:25:50 2011, 美东)
到底是什么？哪里有具体的描述？
是不是指的是下面的三个问题？
1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
number?
2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
numbers?
3. 给定数组size 是 n-m, 1,....n中的m个数missing, 求如何找出那个m个missing
numbers? (假设 m < n/2).
是不是上面的题都有O(n) solution? |
G****A
发帖数: 4160 | 2 如果不考虑空间上的开销(extra space of size n),时间复杂度上很容易控制到O(n) -
counting sort?
但是如果想把空间开销控制在O(1),同时时间复杂度控制到O(n)， 暂时没想到好办法...
【在 c*********t 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: cookiesweet (apple), 信区: JobHunting
: 标 题: 关于那个经典的missing number的题
: 发信站: BBS 未名空间站 (Tue Jun 28 03:25:50 2011, 美东)
: 到底是什么？哪里有具体的描述？
: 是不是指的是下面的三个问题？
: 1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
: number?
: 2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
: numbers?
|
g*****y
发帖数: 7271 | 3 全加起来是不是和sort一样，算nlogn呢？
-
...
【在 G****A 的大作中提到】
: 如果不考虑空间上的开销(extra space of size n),时间复杂度上很容易控制到O(n) -
: counting sort?
: 但是如果想把空间开销控制在O(1),同时时间复杂度控制到O(n)， 暂时没想到好办法...
|
t****t
发帖数: 6806 | 4 你把N个数加起来为什么需要N log N?
【在 g*****y 的大作中提到】
: 全加起来是不是和sort一样，算nlogn呢？
:
: -
: ...
|
g*****y
发帖数: 7271 | 5 如果N很大的话，位数就多，位数不就是logN么。所以和所谓的
bucket sort差不多，如果N不是很大，可以认为O(1)。如果
N真的很大，那就应该是logN了吧？
【在 t****t 的大作中提到】
: 你把N个数加起来为什么需要N log N?
|
t****t
发帖数: 6806 | 6 严格的说这样当然也对了, 不过一般都不这么算吧.
【在 g*****y 的大作中提到】
: 如果N很大的话，位数就多，位数不就是logN么。所以和所谓的
: bucket sort差不多，如果N不是很大，可以认为O(1)。如果
: N真的很大，那就应该是logN了吧？
|
D*******a
发帖数: 3688 | 7 Is it possible to do 3 in O(n) time and O(m) space for arbitrary m
【在 c*********t 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: cookiesweet (apple), 信区: JobHunting
: 标 题: 关于那个经典的missing number的题
: 发信站: BBS 未名空间站 (Tue Jun 28 03:25:50 2011, 美东)
: 到底是什么？哪里有具体的描述？
: 是不是指的是下面的三个问题？
: 1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
: number?
: 2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
: numbers?
|
P********e
发帖数: 2610 | 8 这哪对了?
【在 t****t 的大作中提到】
: 严格的说这样当然也对了, 不过一般都不这么算吧.
|
g*****y
发帖数: 7271 | 9 哦，哪不对了？ 加两个一千多位的数，不得是（1000×常数）左右的运算量？
【在 P********e 的大作中提到】
: 这哪对了?
|
G****A
发帖数: 4160 | 10 complexity的定义不是这样的。
这道题网上有讨论，你自己艘艘
【在 g*****y 的大作中提到】
: 哦，哪不对了？ 加两个一千多位的数，不得是（1000×常数）左右的运算量？
|
|
|
s********v
发帖数: 288 | 11 BigInteger好像就是这么做的吧
【在 t****t 的大作中提到】
: 严格的说这样当然也对了, 不过一般都不这么算吧.
|
b********h
发帖数: 119 | 12 那加3个哪，加4个，。。。，加n个？
【在 g*****y 的大作中提到】
: 哦，哪不对了？ 加两个一千多位的数，不得是（1000×常数）左右的运算量？
|
g*****y
发帖数: 7271 | 13 那不就是我说的nlogn了么？？？？ @_@
【在 b********h 的大作中提到】
: 那加3个哪，加4个，。。。，加n个？
|
g*****y
发帖数: 7271 | 14 哦，complexity 有新的定义了么？ 看来我又过时了。呵呵
【在 G****A 的大作中提到】
: complexity的定义不是这样的。
: 这道题网上有讨论，你自己艘艘
|
h**********c
发帖数: 4120 | 15 好像可以binary search 伐？
log (n) not necessarily m log (n).
【在 c*********t 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: cookiesweet (apple), 信区: JobHunting
: 标 题: 关于那个经典的missing number的题
: 发信站: BBS 未名空间站 (Tue Jun 28 03:25:50 2011, 美东)
: 到底是什么？哪里有具体的描述？
: 是不是指的是下面的三个问题？
: 1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
: number?
: 2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
: numbers?
|
G****A
发帖数: 4160 | 16 complexity: Number of basic operations performed as a function of problem
size. 如果the problem (of size n) requires n次"+"运算, complexity 就是O(n),我
不明白跟位数有什么关系？
你说的“如果N很大的话，位数就多，位数不就是logN么”。你是不是把size of problem和size of
operand混淆了..?
【在 g*****y 的大作中提到】
: 哦，complexity 有新的定义了么？ 看来我又过时了。呵呵
|
t****t
发帖数: 6806 | 17 basic operation implies that input is bounded in a proper range. for not-so-
big number, adding 2 number is a basic operation. that's the common case.
however there exists cases that adding 2 very big number is multiple basic
operations. for example, doing encrypt/decrypt, often you need to deal with
1024-bit numbers. obviously the number of bit is a big factor of complexity.
,我
problem和size of
【在 G****A 的大作中提到】
: complexity: Number of basic operations performed as a function of problem
: size. 如果the problem (of size n) requires n次"+"运算, complexity 就是O(n),我
: 不明白跟位数有什么关系？
: 你说的“如果N很大的话，位数就多，位数不就是logN么”。你是不是把size of problem和size of
: operand混淆了..?
|
p***o
发帖数: 1252 | 18 Maybe, construct a polynomial with the missing numbers as roots
and then solve it.
【在 D*******a 的大作中提到】
: Is it possible to do 3 in O(n) time and O(m) space for arbitrary m
|
P********e
发帖数: 2610 | 19 麻烦你证明一下,你们所说的加法复杂度: O (logN)
so-
with
complexity.
【在 t****t 的大作中提到】
: basic operation implies that input is bounded in a proper range. for not-so-
: big number, adding 2 number is a basic operation. that's the common case.
: however there exists cases that adding 2 very big number is multiple basic
: operations. for example, doing encrypt/decrypt, often you need to deal with
: 1024-bit numbers. obviously the number of bit is a big factor of complexity.
:
: ,我
: problem和size of
|
P********e
发帖数: 2610 | 20 不知道他们的理论从什么地方来的,反正算法理论上你的对的.
,我
problem和size of
【在 G****A 的大作中提到】
: complexity: Number of basic operations performed as a function of problem
: size. 如果the problem (of size n) requires n次"+"运算, complexity 就是O(n),我
: 不明白跟位数有什么关系？
: 你说的“如果N很大的话，位数就多，位数不就是logN么”。你是不是把size of problem和size of
: operand混淆了..?
|
|
|
t****t
发帖数: 6806 | 21 the original problem is to add 1~N. the maximum bit width is propotional to
logN, of course.
【在 P********e 的大作中提到】
: 麻烦你证明一下,你们所说的加法复杂度: O (logN)
:
: so-
: with
: complexity.
|
P********e
发帖数: 2610 | 22 要证明sum(1~N) 复杂度是O(NlogN),需要证明加法复杂度O (logN)
只想说,这是不对的.不知道你们从什么地方学的.
BTW, 你对他比对我友善多了.....
to
【在 t****t 的大作中提到】
: the original problem is to add 1~N. the maximum bit width is propotional to
: logN, of course.
|
G****A
发帖数: 4160 | 23 thanks for clarifying. Now, I see how we understand it differently: |
G****A
发帖数: 4160 | 24 严格来说，他们说的是# of computations, 我们说的是computational complexity。
【在 P********e 的大作中提到】
: 不知道他们的理论从什么地方来的,反正算法理论上你的对的.
:
: ,我
: problem和size of
|
g*****y
发帖数: 7271 | 25 其实我最初以为你想到全加的做法，但是你说你不知道怎么实现O(N)运算量，O(1)
storage的方法，我就想你是不是认为一次加法是O(logN)。现在看来不是这样，呵呵
另外，complexity 就是 # of basic operations，没有区别的。
比方说，字符串搜索问题，不管字符串有多长，每个字符就是8bit或32bit，不会有
变化，所以一次字符比较可以认为是常数运算量。
再比方sorting，不管sort多少个数，所有的数可以都采用float（4bytes），即使
数据个数超出2^32, 只是数串里有重复而已，并不影响sorting，所以可以认为一次比较
是常数运算量。
这个题里面，数据个数和数据范围是直接相关的（相等），这种情况，我们严格来说，
当然
不能认为加法是常数运算量了，对不对？
举个例子，这题另一种做法是全部数乘起来跟N!做个除法，也能找出missing number，
但是你如果还是不考虑溢出的可能性的话，或者仍然认为乘法是常数运算量的话，
是不是有点太搞笑了？而且这题里面不管乘法加法，都是不能有任何精度损失，所以我们
不能说把数转成float来算，是不是？
【在 G****A 的大作中提到】
: 严格来说，他们说的是# of computations, 我们说的是computational complexity。
|
t****t
发帖数: 6806 | 26 不用在意gagama和paulpierce说什么, 你说的他们听不懂是很正常的.
比较
【在 g*****y 的大作中提到】
: 其实我最初以为你想到全加的做法，但是你说你不知道怎么实现O(N)运算量，O(1)
: storage的方法，我就想你是不是认为一次加法是O(logN)。现在看来不是这样，呵呵
: 另外，complexity 就是 # of basic operations，没有区别的。
: 比方说，字符串搜索问题，不管字符串有多长，每个字符就是8bit或32bit，不会有
: 变化，所以一次字符比较可以认为是常数运算量。
: 再比方sorting，不管sort多少个数，所有的数可以都采用float（4bytes），即使
: 数据个数超出2^32, 只是数串里有重复而已，并不影响sorting，所以可以认为一次比较
: 是常数运算量。
: 这个题里面，数据个数和数据范围是直接相关的（相等），这种情况，我们严格来说，
: 当然
|
N********n
发帖数: 8363 | 27
1) If there is 1 missing then find it in O(N) using divide and conquer.
method: use n/2 as pivot to swap & split the array. Find out which half
is short by one. Re-swap and re-split the missing half til you find the
missing # out. The complexity is N + n/2 + n/4 ... = 2N which is O(N).
2) If there are 2 missing then S&S the array with n/2. If both halves are
short by one then you reduce the problem to two type-1 problems of half
the size so the complexity is N + 2(N/2) + 2(N/2) = 3N which is O(N). If
only one half is short by 2 then you reduce the size of the problem by
half so keep S&S the shorter half til you find out what the two #s are.
The complexity is less than 3N which is O(N). So either way it's O(N).
...
3) If there are m missing then S&S the array with n/2 again. The result
is one half has i missing #s and the other j, i + j = m. If both i and j
are greater than 1 then you reduce the problem to the previously solved
type-i & type-j problems, which are both O(N) so the complexity is O(N).
If either i or j is zero then you reduce the size of the problem by half
so keep S&S till you either reduce it into smaller type-i problems or
find out all missing #s in one half. The complexity is O(m * N).
If m is O(lg N) then it's no longer efficient. In that case you might as
well sort the whole array to find out which ones are missing.
【在 c*********t 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: cookiesweet (apple), 信区: JobHunting
: 标 题: 关于那个经典的missing number的题
: 发信站: BBS 未名空间站 (Tue Jun 28 03:25:50 2011, 美东)
: 到底是什么？哪里有具体的描述？
: 是不是指的是下面的三个问题？
: 1. 给定数组size 是 n-1, 1,....n中的一个数missing, 求如何找出那个missing
: number?
: 2. 给定数组size 是 n-2, 1,....n中的两个数missing, 求如何找出那两个missing
: numbers?
|
g*****y
发帖数: 7271 | 28 如果把原数据序列改变了，算O(N) storage，还是算O(1)？
【在 N********n 的大作中提到】
:
: 1) If there is 1 missing then find it in O(N) using divide and conquer.
: method: use n/2 as pivot to swap & split the array. Find out which half
: is short by one. Re-swap and re-split the missing half til you find the
: missing # out. The complexity is N + n/2 + n/4 ... = 2N which is O(N).
: 2) If there are 2 missing then S&S the array with n/2. If both halves are
: short by one then you reduce the problem to two type-1 problems of half
: the size so the complexity is N + 2(N/2) + 2(N/2) = 3N which is O(N). If
: only one half is short by 2 then you reduce the size of the problem by
: half so keep S&S the shorter half til you find out what the two #s are.
|
G****A
发帖数: 4160 | 29 你是码工，别人是研究算法的，看问题的focus不一样,互相听不懂很正常...
讨论问题而已，范的着这么说话。
【在 t****t 的大作中提到】
: 不用在意gagama和paulpierce说什么, 你说的他们听不懂是很正常的.
:
: 比较
|
c*********t
发帖数: 2921 | 30 Thanks.
In your answer to 3), what do you mean by "S&S"?
好像有人在jobhunting 很久以前提到过，把数字归位，就是说把数字放到在数组中应
该的位置，比如1->A[0], 2->A[1], ....然后看哪些位置的数字不对，就说明那个
index对应的数missing,不过好像是有m个数missing,有点tricky,能否忘这个方向想想？
谢谢！
【在 N********n 的大作中提到】
:
: 1) If there is 1 missing then find it in O(N) using divide and conquer.
: method: use n/2 as pivot to swap & split the array. Find out which half
: is short by one. Re-swap and re-split the missing half til you find the
: missing # out. The complexity is N + n/2 + n/4 ... = 2N which is O(N).
: 2) If there are 2 missing then S&S the array with n/2. If both halves are
: short by one then you reduce the problem to two type-1 problems of half
: the size so the complexity is N + 2(N/2) + 2(N/2) = 3N which is O(N). If
: only one half is short by 2 then you reduce the size of the problem by
: half so keep S&S the shorter half til you find out what the two #s are.
|
|
|
h****o
发帖数: 2455 | 31 actually lz and thrust are right. talking about number problems, if you
assume numbers are stored in binary form, the size is logN itself. This is
the nuance in complexity theory.
【在 G****A 的大作中提到】
: 你是码工，别人是研究算法的，看问题的focus不一样,互相听不懂很正常...
: 讨论问题而已，范的着这么说话。
|
g***s
发帖数: 3811 | 32 M个missing一样可以。这个方法做两遍就可以了。
Thanks.In your answer to 3), what do you mean by "S
★ Sent from iPhone App: iReader Mitbbs Lite 7.20
【在 c*********t 的大作中提到】
: Thanks.
: In your answer to 3), what do you mean by "S&S"?
: 好像有人在jobhunting 很久以前提到过，把数字归位，就是说把数字放到在数组中应
: 该的位置，比如1->A[0], 2->A[1], ....然后看哪些位置的数字不对，就说明那个
: index对应的数missing,不过好像是有m个数missing,有点tricky,能否忘这个方向想想？
: 谢谢！
|
N********n
发帖数: 8363 | 33
Hmmm that's a better strategy.
Input: A[n-m], B[m];
Init B to all flags;
for (i = 0; i < n - m; i++) {
t = a[i]; a[i] = flag;
while (t <= n-m && a[t] != flag) {
t1 = at[t]; a[t] = t; t = t1;
}
if (t > n-m)
{
B[t - n + m] = t;
a[i] = flag;
}
else
a[t] = t;
}
Scan through A and B. Flags indicate missing ones. Each element in the
for loop is accessed at most constant times so it's O(N).
【在 c*********t 的大作中提到】
: Thanks.
: In your answer to 3), what do you mean by "S&S"?
: 好像有人在jobhunting 很久以前提到过，把数字归位，就是说把数字放到在数组中应
: 该的位置，比如1->A[0], 2->A[1], ....然后看哪些位置的数字不对，就说明那个
: index对应的数missing,不过好像是有m个数missing,有点tricky,能否忘这个方向想想？
: 谢谢！
|
P********e
发帖数: 2610 | 34 有什么reference说，the size of number is LogN itself?
【在 h****o 的大作中提到】
: actually lz and thrust are right. talking about number problems, if you
: assume numbers are stored in binary form, the size is logN itself. This is
: the nuance in complexity theory.
|
P********e
发帖数: 2610 | 35 我不同意你的说法是因为你abuse big O notation.
比较
【在 g*****y 的大作中提到】
: 其实我最初以为你想到全加的做法，但是你说你不知道怎么实现O(N)运算量，O(1)
: storage的方法，我就想你是不是认为一次加法是O(logN)。现在看来不是这样，呵呵
: 另外，complexity 就是 # of basic operations，没有区别的。
: 比方说，字符串搜索问题，不管字符串有多长，每个字符就是8bit或32bit，不会有
: 变化，所以一次字符比较可以认为是常数运算量。
: 再比方sorting，不管sort多少个数，所有的数可以都采用float（4bytes），即使
: 数据个数超出2^32, 只是数串里有重复而已，并不影响sorting，所以可以认为一次比较
: 是常数运算量。
: 这个题里面，数据个数和数据范围是直接相关的（相等），这种情况，我们严格来说，
: 当然
|
t****t
发帖数: 6806 | 36 i am speechless.
【在 P********e 的大作中提到】
: 有什么reference说，the size of number is LogN itself?
|
