m**q
发帖数: 189 | 1 Finding a duplicated integer. Given a read-only array of n integers between
1 and n-1, design an O(n) time algorithm to find a duplicated integer. Use
only O(1) space. Hint: equivalent to finding a loop in a singly linked
structure.
看了提示好像更糊涂了
read-only array, O(n) time and O(1) space,而且不限定只有一个interger
missing，貌似没办法啊.. |
d********y
发帖数: 2114 | 2 可以把数组元素的值看着指标。
这样就像链表了。
不过觉得也不能O(n)。 |
f*******t
发帖数: 7549 | 3 “Hint: equivalent to finding a loop in a singly linked
structure.”
弄两个index，一个每次前进1，另一个前进2的办法？不像是O(n)时间内的算法 |
s**x
发帖数: 405 | 4 This is exactly equivalent to finding loop in a singly linked list.
The singly linked list is defined with entry A[0] of the input array as the
HEAD node, and the numeric value of each array element as the array index
for the NEXT node. Since every array element A[i] is between 1..(n-1), all
the nodes have valid NEXT node pointers. Thus by sequentially traversing the
list you will encounter a loop.
Just use two iterators I1 and I2, initialized to A[0] and A[A[0]]. Then
while (I1 != I2), let I1 = A[I1] and I2 = A[A[I2]] for each iteration. This
is O(n) because the loop contains no more than n elements. |
r*******g
发帖数: 1335 | 5 真牛，太巧妙了，关键是如何和这个题目联系起来，佩服佩服。
咋一看觉得区别很大，稍微画一下确实如此。
the
the
This
【在 s**x 的大作中提到】
: This is exactly equivalent to finding loop in a singly linked list.
: The singly linked list is defined with entry A[0] of the input array as the
: HEAD node, and the numeric value of each array element as the array index
: for the NEXT node. Since every array element A[i] is between 1..(n-1), all
: the nodes have valid NEXT node pointers. Thus by sequentially traversing the
: list you will encounter a loop.
: Just use two iterators I1 and I2, initialized to A[0] and A[A[0]]. Then
: while (I1 != I2), let I1 = A[I1] and I2 = A[A[I2]] for each iteration. This
: is O(n) because the loop contains no more than n elements.
|
s**x
发帖数: 405 | 6 But wait a minute, this is still not completely solved. If only given O(1)
space, then you can't easily backtrack. When you encounter the loop, how do
you go back to find the place where two nodes point to the same node? |
c*********t
发帖数: 2921 | 7 http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#
do
【在 s**x 的大作中提到】
: But wait a minute, this is still not completely solved. If only given O(1)
: space, then you can't easily backtrack. When you encounter the loop, how do
: you go back to find the place where two nodes point to the same node?
|
c**j
发帖数: 103 | 8 求大牛指正，
这个为什么不能求和 sum1
减去 等差数列的和 sum2，因为1 to n-1
sum1-sum2 is the duplicated number? |
y*******g
发帖数: 6599 | 9 没说只有一个重复。
可能有多个重复
【在 c**j 的大作中提到】
: 求大牛指正，
: 这个为什么不能求和 sum1
: 减去 等差数列的和 sum2，因为1 to n-1
: sum1-sum2 is the duplicated number?
|
c**j
发帖数: 103 | 10 不是
of *n* integers between 1 and *n-1*
e.g 100 个数 between 1-99？
不过确实不是太清楚 |
|
|
m****i
发帖数: 650 | 11 check cycle的方法，不对吧
如果
array 1 2 3 3 4
index 1 2 3 4 5
第一个就infinite loop了 |
q*****9
发帖数: 7 | 12
between
Is the array sorted?
【在 m**q 的大作中提到】
: Finding a duplicated integer. Given a read-only array of n integers between
: 1 and n-1, design an O(n) time algorithm to find a duplicated integer. Use
: only O(1) space. Hint: equivalent to finding a loop in a singly linked
: structure.
: 看了提示好像更糊涂了
: read-only array, O(n) time and O(1) space,而且不限定只有一个interger
: missing，貌似没办法啊..
|
m**q
发帖数: 189 | 13 题目中说明了，index是 0~n-1,value是1~n-1，
所以a[0]的值一定在1~n-1,你说的情况不会出现。
不过这是这道题的一个很强的限制条件。如果value
的范围是0~n-1，那么检查cycle的方法不能用于
解这题，因为会有local cycle的情况，无法保证
找到cycle，就像你说的
index 0 1 2 3 4
value 4 2 2 3 0
dup是2，但是check cycle只能检查到0，4构成的环，
无法找到2这个dup。只是这道题目对取值的限制
保证了这种情况不会发生。
【在 m****i 的大作中提到】
: check cycle的方法，不对吧
: 如果
: array 1 2 3 3 4
: index 1 2 3 4 5
: 第一个就infinite loop了
|
C*******l
发帖数: 1198 | 14 如果是sorted的就很好做。找邻居就行了。不是sorted的话就真的不知怎样才能O(1)
space了。 |
a*******6
发帖数: 520 | 15 Suppose the array is A[1]... A[n], and each A[i] \in {1, ..., n-1}
Corrected method:
1. Start from A[n] instead of A[1]
2. Once I1 == I2, use another O(N) time to find the length of the cycle
3. Then start from A[n] again: set I1 = n and I2 = A[A[A[A[I1]]]] (if the
cycle's length is 4); repeat I1 = A[I1] and I2 = A[I2] until I1 == I2
the
the
This
【在 s**x 的大作中提到】
: This is exactly equivalent to finding loop in a singly linked list.
: The singly linked list is defined with entry A[0] of the input array as the
: HEAD node, and the numeric value of each array element as the array index
: for the NEXT node. Since every array element A[i] is between 1..(n-1), all
: the nodes have valid NEXT node pointers. Thus by sequentially traversing the
: list you will encounter a loop.
: Just use two iterators I1 and I2, initialized to A[0] and A[A[0]]. Then
: while (I1 != I2), let I1 = A[I1] and I2 = A[A[I2]] for each iteration. This
: is O(n) because the loop contains no more than n elements.
|
e***s
发帖数: 799 | 16 应该就是150题的2.5吧。中间有个TRICK，meet point在K STEP BEFORE LOOP START
所以当n1, n2相遇，把n1放回数组头，在一人走一步，再次相遇就是dup了 |
