g***j
发帖数: 1275 | 1 一个无序array，n个整数，每个整数的range是1到n－1，这样就至少有一个重复，要求
找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
度比n的平方好。 |
l*********8
发帖数: 4642 | 2 binary search n*logn
比n
【在 g***j 的大作中提到】
: 一个无序array，n个整数，每个整数的range是1到n－1，这样就至少有一个重复，要求
: 找出其中任意一个重复。要求，array只能读，不能改，不能用额外的空间。时间复杂
: 度比n的平方好。
|
w********s
发帖数: 1570 | 3 xor呀，这题都快老掉牙了
A[0] ^ A[1] ^ ... A[n - 1] ^ 1 ^ 2 ^ ... n - 1 |
w********s
发帖数: 1570 | 4 举个例子
A={1,2,2,3}
那么x = 1^2^2^3^1^2^3
因为两个相同的异或 = 0;
所以剩下就是2 |
l*********8
发帖数: 4642 | 5 可能有多个重复
【在 w********s 的大作中提到】
: 举个例子
: A={1,2,2,3}
: 那么x = 1^2^2^3^1^2^3
: 因为两个相同的异或 = 0;
: 所以剩下就是2
|
w********s
发帖数: 1570 | 6 没说是排序的，你咋search?
【在 l*********8 的大作中提到】
: binary search n*logn
:
: 比n
|
b**********d
发帖数: 7 | |
M**a
发帖数: 848 | 8 没想到。不过有多个重复。不能xor。 没排序不能二分。全部一个个比就是n2的复杂度
吧。 |
w********s
发帖数: 1570 | 9 你确认比平方好？
【在 b**********d 的大作中提到】
: 从1到n-1一个一个找，不就比平方好？
|
l*********8
发帖数: 4642 | 10 假如是有序的, 就是log n了
【在 w********s 的大作中提到】
: 没说是排序的，你咋search?
|
|
|
h*****n
发帖数: 92 | |
l*******e
发帖数: 309 | 12
我觉得可以。每次循环分把区间切俩半计落入区间的个数，在多的那个区间继续找。
【在 l*********8 的大作中提到】
: binary search n*logn
:
: 比n
|
b**********d
发帖数: 7 | 13 题目只是说比n的平方好，
(n-1)*n难道不比n的平方好？
【在 w********s 的大作中提到】
: 你确认比平方好？
|
o***g
发帖数: 2784 | 14 二分法，将整个区间分两半，然后确定哪一半里有重复，再在这一半里找
比如开始是[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的平方好。
|
c******t
发帖数: 133 | 15 不太对，[1, 2, 1, 2]怎么分？
【在 o***g 的大作中提到】
: 二分法，将整个区间分两半，然后确定哪一半里有重复，再在这一半里找
: 比如开始是[1 , n/2] [n/2 , (n-1)]
: 可以将所有在1到n/2之间的所有数都数一下，n/2到n-1之间的所有数也都数一下，大于
: 应该有的个数的话，这里就是有重复的，另一半舍弃
: 再在这一半里分成两部分继续数数
: 复杂度应该是O(nlogn)
|
s********k
发帖数: 2352 | 16 每个整数的range是1到n－1 这个条件应该是关键。 记得有个题是range是1到n－1的数
排序。 |
P******r
发帖数: 1342 | 17 按顺序从头开始扫，
如果A[i] == A[A[i]]，就找到了。
如果不等，就把A[i]和A[A[i]]调换。
这样差不多是O(n)吧？ |
s*****r
发帖数: 108 | 18 二分搜索，异或，分治，n*(n-1)，交换元素…
这都是… |
w********s
发帖数: 1570 | 19 不能改变数组，没看见？
【在 P******r 的大作中提到】
: 按顺序从头开始扫，
: 如果A[i] == A[A[i]]，就找到了。
: 如果不等，就把A[i]和A[A[i]]调换。
: 这样差不多是O(n)吧？
|
o***g
发帖数: 2784 | 20 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]怎么分？
|
|
|
d**k
发帖数: 797 | 21 那你用他的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了
|
Q**F
发帖数: 995 | 22 为什么需要保存数组？
只需要一个保存个数的变量就可以了。
【在 d**k 的大作中提到】
: 那你用他的value来分组
: 用什么来保存这个组呢？
: 说了不让用另外的数据结构阿
|
o***g
发帖数: 2784 | 23 只有两个区间还是连续的，所以只用4个变量就行了，存最大最小值，在stack里的变量
应该不算额外空间吧
每个区间的count也需要1个变量
【在 d**k 的大作中提到】
: 那你用他的value来分组
: 用什么来保存这个组呢？
: 说了不让用另外的数据结构阿
|
d**k
发帖数: 797 | 24 那就是说每次算个数都要scan n个元素
而不是从之前的scan 结果继续过滤，对吧？
确实是nlog(n)
【在 Q**F 的大作中提到】
: 为什么需要保存数组？
: 只需要一个保存个数的变量就可以了。
|
d**k
发帖数: 797 | 25 这个解释没看懂
什么区间？
比如说1231234这个组
怎么个区间法？
【在 o***g 的大作中提到】
: 只有两个区间还是连续的，所以只用4个变量就行了，存最大最小值，在stack里的变量
: 应该不算额外空间吧
: 每个区间的count也需要1个变量
|
Q**F
发帖数: 995 | 26 你觉得这个可行吗？
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
if(v[i] >=start && v[i] <= (start+end)/2)
{
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
发帖数: 2784 | 27 这个数组按照题目是一共7个数，我们就知道这里包含的整数是1到6这个区间内的整数
将1到6这个区间分成1到3和4到6两个区间去统计各有多少个数，必然会有一个区间的数
的个数是超过3个的
【在 d**k 的大作中提到】
: 这个解释没看懂
: 什么区间？
: 比如说1231234这个组
: 怎么个区间法？
|
d**k
发帖数: 797 | 28 我理解这个
那个最大最小值是什么意思?
【在 o***g 的大作中提到】
: 这个数组按照题目是一共7个数，我们就知道这里包含的整数是1到6这个区间内的整数
: 将1到6这个区间分成1到3和4到6两个区间去统计各有多少个数，必然会有一个区间的数
: 的个数是超过3个的
|
d**k
发帖数: 797 | 29 对,这个跟我的理解一样
【在 Q**F 的大作中提到】
: 你觉得这个可行吗？
: class Solution
: {
: public:
: int findDup(vector v)
: {
: int start =1; //搜索区间的下限
: int end = v.size()-1; //搜素区间的上限
: int count = 0; //搜索区间的个数
: while(start < end)
|
o***g
发帖数: 2784 | 30 就是start end
【在 d**k 的大作中提到】
: 我理解这个
: 那个最大最小值是什么意思?
|
|
|
f**********3
发帖数: 11 | |
c******t
发帖数: 133 | 32 理解了，确实可行，也就是上面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了
|
l**********i
发帖数: 84 | 33 binary search这个办法感觉没完全用上1～n-1这个条件，是不是可以用index来做，就
跟first missing positive number一样？ |
P******r
发帖数: 1342 | 34 有O(n)的算法。这题可以转化成linked list找Loop start |
