绿了之后的状态变化# Immigration - 落地生根
g*j
1 楼
一个无序array，n个整数，每个整数的range是1到n－1，这样就至少有一个重复，要求
找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
度比n的平方好。
找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
度比n的平方好。
e*e
2 楼
在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
card production的状态变化来来回回三次。其中register status两次，card sent to
production，卡制成，被USPS收到的notice各一封。
最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
denied了，大概是因为我485在combo卡前批准的原因吧。
关于card的邮寄，最后收到的e-mail是这样的
The USPS reported that they picked up mail from USCIS containing your new
card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
use this number at 。。。
他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
以track的USPS service，应该不是需要签名的service吧？否则岂不是还要在家里留着
等送上门？
总的来说我的绿卡之路还算顺利，跟非常nice的老板和大老板的支持也很有关系。倒反
而是我自己太拖。485的过程也算挺快的，从file到批准两个月。
140详细信息在这里
http://www.mitbbs.com/article_t0/Immigration/32554339.html
485 timeline在这里
http://www.mitbbs.com/article_t0/Immigration/32713373.html
祝大家绿卡之路顺利。
card production的状态变化来来回回三次。其中register status两次，card sent to
production，卡制成，被USPS收到的notice各一封。
最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
denied了，大概是因为我485在combo卡前批准的原因吧。
关于card的邮寄，最后收到的e-mail是这样的
The USPS reported that they picked up mail from USCIS containing your new
card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
use this number at 。。。
他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
以track的USPS service，应该不是需要签名的service吧？否则岂不是还要在家里留着
等送上门？
总的来说我的绿卡之路还算顺利，跟非常nice的老板和大老板的支持也很有关系。倒反
而是我自己太拖。485的过程也算挺快的，从file到批准两个月。
140详细信息在这里
http://www.mitbbs.com/article_t0/Immigration/32554339.html
485 timeline在这里
http://www.mitbbs.com/article_t0/Immigration/32713373.html
祝大家绿卡之路顺利。
l*8
3 楼
binary search n*logn
比n
【在 g***j 的大作中提到】
: 一个无序array，n个整数，每个整数的range是1到n－1，这样就至少有一个重复，要求
: 找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
: 度比n的平方好。
比n
【在 g***j 的大作中提到】
: 一个无序array，n个整数，每个整数的range是1到n－1，这样就至少有一个重复，要求
: 找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
: 度比n的平方好。
A*n
4 楼
cong!你可以打电话要tracking number
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
w*s
5 楼
xor呀，这题都快老掉牙了
A[0] ^ A[1] ^ ... A[n - 1] ^ 1 ^ 2 ^ ... n - 1
A[0] ^ A[1] ^ ... A[n - 1] ^ 1 ^ 2 ^ ... n - 1
V*A
6 楼
gx!
Baozi!
Baozi!
w*s
7 楼
举个例子
A={1,2,2,3}
那么x = 1^2^2^3^1^2^3
因为两个相同的异或 = 0;
所以剩下就是2
A={1,2,2,3}
那么x = 1^2^2^3^1^2^3
因为两个相同的异或 = 0;
所以剩下就是2
x*n
8 楼
cong!
l*8
9 楼
可能有多个重复
【在 w********s 的大作中提到】
: 举个例子
: A={1,2,2,3}
: 那么x = 1^2^2^3^1^2^3
: 因为两个相同的异或 = 0;
: 所以剩下就是2
【在 w********s 的大作中提到】
: 举个例子
: A={1,2,2,3}
: 那么x = 1^2^2^3^1^2^3
: 因为两个相同的异或 = 0;
: 所以剩下就是2
w*e
10 楼
cong！！
to
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
to
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
w*s
11 楼
没说是排序的，你咋search?
【在 l*********8 的大作中提到】
: binary search n*logn
:
: 比n
【在 l*********8 的大作中提到】
: binary search n*logn
:
: 比n
w*i
12 楼
cong
b*d
13 楼
从1到n-1一个一个找，不就比平方好？
w*s
14 楼
cong
M*a
15 楼
没想到。不过有多个重复。不能xor。 没排序不能二分。全部一个个比就是n2的复杂度
吧。
吧。
u*s
16 楼
congrats!
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
w*s
17 楼
你确认比平方好？
【在 b**********d 的大作中提到】
: 从1到n-1一个一个找，不就比平方好？
【在 b**********d 的大作中提到】
: 从1到n-1一个一个找，不就比平方好？
g*2
18 楼
big big cong!
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
l*8
19 楼
假如是有序的, 就是log n了
【在 w********s 的大作中提到】
: 没说是排序的，你咋search?
【在 w********s 的大作中提到】
: 没说是排序的，你咋search?
s*4
20 楼
Cong
No need to sign
The card will be waiting for you in your mailbox
to
★ 发自iPhone App: ChineseWeb 7.7
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
No need to sign
The card will be waiting for you in your mailbox
to
★ 发自iPhone App: ChineseWeb 7.7
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
h*n
21 楼
只读数组，不能用排序啥的
e*e
22 楼
Thanks a lot.
【在 s******4 的大作中提到】
: Cong
: No need to sign
: The card will be waiting for you in your mailbox
:
: to
: ★ 发自iPhone App: ChineseWeb 7.7
【在 s******4 的大作中提到】
: Cong
: No need to sign
: The card will be waiting for you in your mailbox
:
: to
: ★ 发自iPhone App: ChineseWeb 7.7
l*e
23 楼
我觉得可以。每次循环分把区间切俩半计落入区间的个数，在多的那个区间继续找。
【在 l*********8 的大作中提到】
: binary search n*logn
:
: 比n
p*p
24 楼
big cong!
b*d
25 楼
题目只是说比n的平方好，
(n-1)*n难道不比n的平方好？
【在 w********s 的大作中提到】
: 你确认比平方好？
(n-1)*n难道不比n的平方好？
【在 w********s 的大作中提到】
: 你确认比平方好？
y*6
26 楼
Cong.
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
o*g
27 楼
二分法，将整个区间分两半，然后确定哪一半里有重复，再在这一半里找
比如开始是[1 , n/2] [n/2 , (n-1)]
可以将所有在1到n/2之间的所有数都数一下，n/2到n-1之间的所有数也都数一下，大于
应该有的个数的话，这里就是有重复的，另一半舍弃
再在这一半里分成两部分继续数数
复杂度应该是O(nlogn)
【在 g***j 的大作中提到】
: 一个无序array，n个整数，每个整数的range是1到n－1，这样就至少有一个重复，要求
: 找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
: 度比n的平方好。
比如开始是[1 , n/2] [n/2 , (n-1)]
可以将所有在1到n/2之间的所有数都数一下，n/2到n-1之间的所有数也都数一下，大于
应该有的个数的话，这里就是有重复的，另一半舍弃
再在这一半里分成两部分继续数数
复杂度应该是O(nlogn)
【在 g***j 的大作中提到】
: 一个无序array，n个整数，每个整数的range是1到n－1，这样就至少有一个重复，要求
: 找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
: 度比n的平方好。
d*n
28 楼
cong!
c*t
29 楼
不太对，[1, 2, 1, 2]怎么分？
【在 o***g 的大作中提到】
: 二分法，将整个区间分两半，然后确定哪一半里有重复，再在这一半里找
: 比如开始是[1 , n/2] [n/2 , (n-1)]
: 可以将所有在1到n/2之间的所有数都数一下，n/2到n-1之间的所有数也都数一下，大于
: 应该有的个数的话，这里就是有重复的，另一半舍弃
: 再在这一半里分成两部分继续数数
: 复杂度应该是O(nlogn)
【在 o***g 的大作中提到】
: 二分法，将整个区间分两半，然后确定哪一半里有重复，再在这一半里找
: 比如开始是[1 , n/2] [n/2 , (n-1)]
: 可以将所有在1到n/2之间的所有数都数一下，n/2到n-1之间的所有数也都数一下，大于
: 应该有的个数的话，这里就是有重复的，另一半舍弃
: 再在这一半里分成两部分继续数数
: 复杂度应该是O(nlogn)
c*t
30 楼
gongxi
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
to
can
【在 e**e 的大作中提到】
: 在收到485 approval e-mail之后，网上status通知的e-mail总共有7封。从decision到
: card production的状态变化来来回回三次。其中register status两次，card sent to
: production，卡制成，被USPS收到的notice各一封。
: 最让人吓一跳的还是今天早上收到的denial notice，仔细一看，还好是combo card被
: denied了，大概是因为我485在combo卡前批准的原因吧。
: 关于card的邮寄，最后收到的e-mail是这样的
: The USPS reported that they picked up mail from USCIS containing your new
: card on January 9, 2013. The USPS tracking number assigned is #DCN. You can
: use this number at 。。。
: 他给了个track option，但是没有给track number。这个觉得很奇怪。还有，既然是可
s*k
31 楼
每个整数的range是1到n－1 这个条件应该是关键。 记得有个题是range是1到n－1的数
排序。
排序。
w*c
32 楼
cong
P*r
33 楼
按顺序从头开始扫，
如果A[i] == A[A[i]]，就找到了。
如果不等，就把A[i]和A[A[i]]调换。
这样差不多是O(n)吧？
如果A[i] == A[A[i]]，就找到了。
如果不等，就把A[i]和A[A[i]]调换。
这样差不多是O(n)吧？
s*1
34 楼
gxgx...希望lz能分享一点材料～～～后人在准备中。。。。
s*r
35 楼
二分搜索，异或，分治，n*(n-1)，交换元素…
这都是…
这都是…
l*g
36 楼
希望多分享点材料
w*s
37 楼
不能改变数组，没看见？
【在 P******r 的大作中提到】
: 按顺序从头开始扫，
: 如果A[i] == A[A[i]]，就找到了。
: 如果不等，就把A[i]和A[A[i]]调换。
: 这样差不多是O(n)吧？
【在 P******r 的大作中提到】
: 按顺序从头开始扫，
: 如果A[i] == A[A[i]]，就找到了。
: 如果不等，就把A[i]和A[A[i]]调换。
: 这样差不多是O(n)吧？
m*e
38 楼
不用签名，我当时的收到的卡就直接放在邮箱里的。
o*g
39 楼
n=4
数组里应该是1-3
1-2一组 3一组，或者1 一组 2-3一组都行
比如选前面这个 1-2应该是2个数，结果是4个，3这个组里是0个数，就将3这组舍弃
1-2这组再分成1一组 2一组
然后，1这组有俩，2这组有俩，先看1这组的话，本来应该是1个数，现在有俩就是1了
【在 c******t 的大作中提到】
: 不太对，[1, 2, 1, 2]怎么分？
数组里应该是1-3
1-2一组 3一组，或者1 一组 2-3一组都行
比如选前面这个 1-2应该是2个数，结果是4个，3这个组里是0个数，就将3这组舍弃
1-2这组再分成1一组 2一组
然后，1这组有俩，2这组有俩，先看1这组的话，本来应该是1个数，现在有俩就是1了
【在 c******t 的大作中提到】
: 不太对，[1, 2, 1, 2]怎么分？
d*k
40 楼
那你用他的value来分组
用什么来保存这个组呢？
说了不让用另外的数据结构阿
【在 o***g 的大作中提到】
: n=4
: 数组里应该是1-3
: 1-2一组 3一组，或者1 一组 2-3一组都行
: 比如选前面这个 1-2应该是2个数，结果是4个，3这个组里是0个数，就将3这组舍弃
: 1-2这组再分成1一组 2一组
: 然后，1这组有俩，2这组有俩，先看1这组的话，本来应该是1个数，现在有俩就是1了
用什么来保存这个组呢？
说了不让用另外的数据结构阿
【在 o***g 的大作中提到】
: n=4
: 数组里应该是1-3
: 1-2一组 3一组，或者1 一组 2-3一组都行
: 比如选前面这个 1-2应该是2个数，结果是4个，3这个组里是0个数，就将3这组舍弃
: 1-2这组再分成1一组 2一组
: 然后，1这组有俩，2这组有俩，先看1这组的话，本来应该是1个数，现在有俩就是1了
Q*F
41 楼
为什么需要保存数组？
只需要一个保存个数的变量就可以了。
【在 d**k 的大作中提到】
: 那你用他的value来分组
: 用什么来保存这个组呢？
: 说了不让用另外的数据结构阿
只需要一个保存个数的变量就可以了。
【在 d**k 的大作中提到】
: 那你用他的value来分组
: 用什么来保存这个组呢？
: 说了不让用另外的数据结构阿
o*g
42 楼
只有两个区间还是连续的，所以只用4个变量就行了，存最大最小值，在stack里的变量
应该不算额外空间吧
每个区间的count也需要1个变量
【在 d**k 的大作中提到】
: 那你用他的value来分组
: 用什么来保存这个组呢？
: 说了不让用另外的数据结构阿
应该不算额外空间吧
每个区间的count也需要1个变量
【在 d**k 的大作中提到】
: 那你用他的value来分组
: 用什么来保存这个组呢？
: 说了不让用另外的数据结构阿
d*k
43 楼
那就是说每次算个数都要scan n个元素
而不是从之前的scan 结果继续过滤，对吧？
确实是nlog(n)
【在 Q**F 的大作中提到】
: 为什么需要保存数组？
: 只需要一个保存个数的变量就可以了。
而不是从之前的scan 结果继续过滤，对吧？
确实是nlog(n)
【在 Q**F 的大作中提到】
: 为什么需要保存数组？
: 只需要一个保存个数的变量就可以了。
d*k
44 楼
这个解释没看懂
什么区间？
比如说1231234这个组
怎么个区间法？
【在 o***g 的大作中提到】
: 只有两个区间还是连续的，所以只用4个变量就行了，存最大最小值，在stack里的变量
: 应该不算额外空间吧
: 每个区间的count也需要1个变量
什么区间？
比如说1231234这个组
怎么个区间法？
【在 o***g 的大作中提到】
: 只有两个区间还是连续的，所以只用4个变量就行了，存最大最小值，在stack里的变量
: 应该不算额外空间吧
: 每个区间的count也需要1个变量
Q*F
45 楼
你觉得这个可行吗？
class Solution
{
public:
int findDup(vector v)
{
int start =1; //搜索区间的下限
int end = v.size()-1; //搜素区间的上限
int count = 0; //搜索区间的个数
while(start < end)
{
for(int i=0; i
{
count++;
}
}
if(count > ((start+end)/2 -start + 1))
{
end = (start+end)/2;
}
else
{
start = (start+end)/2+1;
}
count = 0;
}
return start;
}
}
【在 d**k 的大作中提到】
: 那就是说每次算个数都要scan n个元素
: 而不是从之前的scan 结果继续过滤，对吧？
: 确实是nlog(n)
class Solution
{
public:
int findDup(vector
{
int start =1; //搜索区间的下限
int end = v.size()-1; //搜素区间的上限
int count = 0; //搜索区间的个数
while(start < end)
{
for(int i=0; i
{
count++;
}
}
if(count > ((start+end)/2 -start + 1))
{
end = (start+end)/2;
}
else
{
start = (start+end)/2+1;
}
count = 0;
}
return start;
}
}
【在 d**k 的大作中提到】
: 那就是说每次算个数都要scan n个元素
: 而不是从之前的scan 结果继续过滤，对吧？
: 确实是nlog(n)
o*g
46 楼
这个数组按照题目是一共7个数，我们就知道这里包含的整数是1到6这个区间内的整数
将1到6这个区间分成1到3和4到6两个区间去统计各有多少个数，必然会有一个区间的数
的个数是超过3个的
【在 d**k 的大作中提到】
: 这个解释没看懂
: 什么区间？
: 比如说1231234这个组
: 怎么个区间法？
将1到6这个区间分成1到3和4到6两个区间去统计各有多少个数，必然会有一个区间的数
的个数是超过3个的
【在 d**k 的大作中提到】
: 这个解释没看懂
: 什么区间？
: 比如说1231234这个组
: 怎么个区间法？
d*k
47 楼
我理解这个
那个最大最小值是什么意思?
【在 o***g 的大作中提到】
: 这个数组按照题目是一共7个数，我们就知道这里包含的整数是1到6这个区间内的整数
: 将1到6这个区间分成1到3和4到6两个区间去统计各有多少个数，必然会有一个区间的数
: 的个数是超过3个的
那个最大最小值是什么意思?
【在 o***g 的大作中提到】
: 这个数组按照题目是一共7个数，我们就知道这里包含的整数是1到6这个区间内的整数
: 将1到6这个区间分成1到3和4到6两个区间去统计各有多少个数，必然会有一个区间的数
: 的个数是超过3个的
d*k
48 楼
对,这个跟我的理解一样
【在 Q**F 的大作中提到】
: 你觉得这个可行吗？
: class Solution
: {
: public:
: int findDup(vector v)
: {
: int start =1; //搜索区间的下限
: int end = v.size()-1; //搜素区间的上限
: int count = 0; //搜索区间的个数
: while(start < end)
【在 Q**F 的大作中提到】
: 你觉得这个可行吗？
: class Solution
: {
: public:
: int findDup(vector
: {
: int start =1; //搜索区间的下限
: int end = v.size()-1; //搜素区间的上限
: int count = 0; //搜索区间的个数
: while(start < end)
o*g
49 楼
就是start end
【在 d**k 的大作中提到】
: 我理解这个
: 那个最大最小值是什么意思?
【在 d**k 的大作中提到】
: 我理解这个
: 那个最大最小值是什么意思?
f*3
50 楼
这题能做么？
c*t
51 楼
理解了，确实可行，也就是上面longway2008说得binary search，谢谢
【在 o***g 的大作中提到】
: n=4
: 数组里应该是1-3
: 1-2一组 3一组，或者1 一组 2-3一组都行
: 比如选前面这个 1-2应该是2个数，结果是4个，3这个组里是0个数，就将3这组舍弃
: 1-2这组再分成1一组 2一组
: 然后，1这组有俩，2这组有俩，先看1这组的话，本来应该是1个数，现在有俩就是1了
【在 o***g 的大作中提到】
: n=4
: 数组里应该是1-3
: 1-2一组 3一组，或者1 一组 2-3一组都行
: 比如选前面这个 1-2应该是2个数，结果是4个，3这个组里是0个数，就将3这组舍弃
: 1-2这组再分成1一组 2一组
: 然后，1这组有俩，2这组有俩，先看1这组的话，本来应该是1个数，现在有俩就是1了
l*i
52 楼
binary search这个办法感觉没完全用上1～n-1这个条件，是不是可以用index来做，就
跟first missing positive number一样？
跟first missing positive number一样？
P*r
53 楼
有O(n)的算法。这题可以转化成linked list找Loop start
相关阅读
湾区跳槽H1B transfer+NIW问题自已申请FBI 指纹背景调查会招来麻烦端午节报绿!NSC 485 card production 6/21用AP回国现在的身份就自动没有了吗？I140已经file，pp应该寄到的地址体检可以早点做吗？PP真的比较容易招RFE么？有没有从O1转EB-1的，分享一下经历？为什么律师的eb1b case 比其他的要少很多呢土土问一下装订问题[再次分享]推荐人不需要提供简历而且也不必要是大牛O1和EB1A推荐信怎么区分开？电子签名的pdf推荐信可以吗special handling 到底有什么特别？关于RFE的有效期绿了， TSC， RD 3/23看了张哲瑞的简历， 人生真是艰辛啊6月1号左右tsc收到上千个485？刚看 德国昨天狂殴希腊 4:2 很解气啊