b*******e
发帖数: 217 | 1 array of N integers, 0 < x < N,
find the first repeated element in the array.
do it in linear time and constant space.
I got the answer but guess failed ...
typically how many problems are expected to resolve in one phone interview? |
z*******g
发帖数: 18 | 2 我觉得可以首先建一个int array[N],初始化为0，
然后从所给的N integers array given[i]的第一个开始扫描,i = 0:N-1，如果array[
given[i]]=0,那么就设array[given[i]]=1,如果array[given[i]]已经是1了说明之前出
现过了，所以就结束程序，given[i]就是第一个重复的数。
?
【在 b*******e 的大作中提到】
: array of N integers, 0 < x < N,
: find the first repeated element in the array.
: do it in linear time and constant space.
: I got the answer but guess failed ...
: typically how many problems are expected to resolve in one phone interview?
|
f*****e
发帖数: 2992 | 3 前面讨论过了，看这个thread
http://mitbbs.com/article1/JobHunting/32341161_3_0.html
?
【在 b*******e 的大作中提到】
: array of N integers, 0 < x < N,
: find the first repeated element in the array.
: do it in linear time and constant space.
: I got the answer but guess failed ...
: typically how many problems are expected to resolve in one phone interview?
|
l****i
发帖数: 2772 | 4 what was your answer?
?
【在 b*******e 的大作中提到】
: array of N integers, 0 < x < N,
: find the first repeated element in the array.
: do it in linear time and constant space.
: I got the answer but guess failed ...
: typically how many problems are expected to resolve in one phone interview?
|
l****i
发帖数: 2772 | 5 题目不一样吧。first repeated element怎么定义？
【在 f*****e 的大作中提到】
: 前面讨论过了，看这个thread
: http://mitbbs.com/article1/JobHunting/32341161_3_0.html
:
: ?
|
e***s
发帖数: 799 | 6 Swap吧。
loop array
if(A[i] != i + 1){
if(A[A[i - 1]] == A[i]) return A[i];
swap(A[i], A[A[i - 1]]);
} |
b*******e
发帖数: 217 | 7 example: { 3, 2, 4, 1 3} 3 is the fist repeated.
// const space
for (int i = 0; i < N; i++) {
int x = a[i];
if ( x> 0 ) {
if ( a[x] < 0 ) { // means the xith item has been changed before.
that means X has shown up already
cout << x << endl;
break;
}
else { // means the xth item has not bee changed yet. let us change
the xth item to negative. Also this mean X does not show up yet
a[x] = a[x]- N;
}
}
else { // this x has been changed
//get the orig value first
int orig = x + N;
if ( a[orig] <= 0 ) { // this a[orig] has been hitted before
cout<< orig << endl;
break;
}
else {
a[orig] = a[orig] - N;
}
}
} |
f*****e
发帖数: 2992 | 8 A[i]=-(index of i first appears)*2，顶多扫两遍。
【在 l****i 的大作中提到】
: 题目不一样吧。first repeated element怎么定义？
|
b*******e
发帖数: 217 | 9 not constant space.
【在 z*******g 的大作中提到】
: 我觉得可以首先建一个int array[N],初始化为0，
: 然后从所给的N integers array given[i]的第一个开始扫描,i = 0:N-1，如果array[
: given[i]]=0,那么就设array[given[i]]=1,如果array[given[i]]已经是1了说明之前出
: 现过了，所以就结束程序，given[i]就是第一个重复的数。
:
: ?
|
d******e
发帖数: 164 | 10 int find_dup(int A[], int n) {
for (int i = 0; i < n; i++) {
while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
if (A[i] != i+1) return A[i];
}
}
?
【在 b*******e 的大作中提到】
: array of N integers, 0 < x < N,
: find the first repeated element in the array.
: do it in linear time and constant space.
: I got the answer but guess failed ...
: typically how many problems are expected to resolve in one phone interview?
|
|
|
b*******e
发帖数: 217 | 11 I may miss your point.... how does this work on
34112?
can we find 1?
>>>>
int find_dup(int A[], int n) {
for (int i = 0; i < n; i++) {
while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
if (A[i] != i+1) return A[i];
}
}
?
【在 b*******e 的大作中提到】
: array of N integers, 0 < x < N,
: find the first repeated element in the array.
: do it in linear time and constant space.
: I got the answer but guess failed ...
: typically how many problems are expected to resolve in one phone interview?
|
b*******e
发帖数: 217 | 12 could you give more details?
I did not get it yet. could you use an example to describe your idea?
【在 e***s 的大作中提到】
: Swap吧。
: loop array
: if(A[i] != i + 1){
: if(A[A[i - 1]] == A[i]) return A[i];
: swap(A[i], A[A[i - 1]]);
: }
|
j*****y
发帖数: 1071 | 13 感觉不对
比如
1 2 2 1
你这个找出来的是 2
【在 d******e 的大作中提到】
: int find_dup(int A[], int n) {
: for (int i = 0; i < n; i++) {
: while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
: if (A[i] != i+1) return A[i];
: }
: }
:
: ?
|
h***t
发帖数: 2540 | 14 就应该是2啊， 2 repeat的比1 repeat的早
【在 j*****y 的大作中提到】
: 感觉不对
: 比如
: 1 2 2 1
: 你这个找出来的是 2
|
j*****y
发帖数: 1071 | 15 这么理解吗，感觉应该是 1阿
请楼主来澄清一下
【在 h***t 的大作中提到】
: 就应该是2啊， 2 repeat的比1 repeat的早
|
j*****y
发帖数: 1071 | 16 感觉还是不对，你看看
4 2 2 4 1
这个用他的code跑出来是 4, 按照你的看法，应该是 2
就应该是2啊， 2 repeat的比1 repeat的早
【在 h***t 的大作中提到】
: 就应该是2啊， 2 repeat的比1 repeat的早
|
c*****r
发帖数: 108 | |
j*****y
发帖数: 1071 | 18 你这个扫两遍，第一遍的时候是不是已经把 原来的array 修改了？ 第二遍还怎么搞？
【在 f*****e 的大作中提到】
: A[i]=-(index of i first appears)*2，顶多扫两遍。
|
j*****y
发帖数: 1071 | 19 这个感觉难度不太一样吧?
【在 f*****e 的大作中提到】
: 前面讨论过了，看这个thread
: http://mitbbs.com/article1/JobHunting/32341161_3_0.html
:
: ?
|
j*****y
发帖数: 1071 | 20 xor ? 感觉不太一样吧 ?
【在 c*****r 的大作中提到】
: 位操作不就可以了么？
|
|
|
b*******e
发帖数: 217 | 21 should be 2.
Does my agorithm give 4?
btw, could you give more details about the swap algorithm? I did not get it.
【在 j*****y 的大作中提到】
: 感觉还是不对，你看看
: 4 2 2 4 1
: 这个用他的code跑出来是 4, 按照你的看法，应该是 2
:
: 就应该是2啊， 2 repeat的比1 repeat的早
|
b*******e
发帖数: 217 | 22 Some modificaiton on my code. don't need to use x-N to track whether a X is
hit. Simply use -X is okay.
-------------
are you talking about my algorithm?
It gives 2 for 1221.
(1) go to a[0], 1 -> will change a[1] to 2-4 = -2. the array becomes 1, -2,
2, 1
(2) go to a[1], -2, calculate the original = 4-2 = 2. check a[orig] = a[2] =
2 > 0, so change a[2] to 2-4
= -2. now the array becomes 1, -2, -2, 1. Note here a[2] is changed because
of a[1] originally == 2.
(3) go to a[2], -2, calculate the orignal = 4-2 =2. check a[orig] = [2] = -2
< 0 which indicates it is changed by a[**] = orig = 2 where ** is before 2
(here ** is 1). So 2 is found as the first repeated one.
Below is the code.
// const space
for (int i = 0; i < N; i++) {
int x = a[i];
if ( x> 0 ) {
if ( a[x] < 0 ) { // means the xith item has been changed before.
that means X has shown up already
cout << x << endl;
break;
}
else { // means the xth item has not bee changed yet. let us change
the xth item to negative. Also this mean X does not show up yet
a[x] = -a[x];
}
}
else { // this x has been changed
//get the orig value first
int orig = -x;
if ( a[orig] <= 0 ) { // this a[orig] has been hitted before
cout<< orig << endl;
break;
}
else {
a[orig] = -a[orig];
}
}
}
【在 j*****y 的大作中提到】
: 感觉还是不对，你看看
: 4 2 2 4 1
: 这个用他的code跑出来是 4, 按照你的看法，应该是 2
:
: 就应该是2啊， 2 repeat的比1 repeat的早
|
j*****y
发帖数: 1071 | 23 不是，刚才是说 didiaoge的
正在研究你的 :)
2,
4
because
-2
2
【在 b*******e 的大作中提到】
: Some modificaiton on my code. don't need to use x-N to track whether a X is
: hit. Simply use -X is okay.
: -------------
: are you talking about my algorithm?
: It gives 2 for 1221.
: (1) go to a[0], 1 -> will change a[1] to 2-4 = -2. the array becomes 1, -2,
: 2, 1
: (2) go to a[1], -2, calculate the original = 4-2 = 2. check a[orig] = a[2] =
: 2 > 0, so change a[2] to 2-4
: = -2. now the array becomes 1, -2, -2, 1. Note here a[2] is changed because
|
b*******e
发帖数: 217 | 24 how this work for 24332?
Did I miss anything?
Seems,
i = 0, a[0] = 2 != a[2-1] = 4, so swap a[0] && a[2-1] = a[1]. so the array
is
now 42332.
check if (a[0] = 4 != 0+1 = 1) so return a[0] = 4.
Yet the answer should be 3.
Do I miss anything?
【在 d******e 的大作中提到】
: int find_dup(int A[], int n) {
: for (int i = 0; i < n; i++) {
: while (A[i] != A[A[i]-1]) swap(A[i], A[A[i]-1]);
: if (A[i] != i+1) return A[i];
: }
: }
:
: ?
|
r*********n
发帖数: 4553 | 25 这个题一般的version是 there are N+1 integers ranging from 0 to N-1, find the
repeated integer。显然有且只有一个重复的。用swap归位，如果 arr[arr[i]] ==
arr[i]，就返回arr[i]。
这个问题问the first repeated integer，所以用一个变量存repeated integer seen
so far，每次遇到新的就和这个比较一下。 |
j*****y
发帖数: 1071 | 26 关键是怎么比较，因为那个应该是第一个 repeat number的数或许交换到后面去了
the
seen
【在 r*********n 的大作中提到】
: 这个题一般的version是 there are N+1 integers ranging from 0 to N-1, find the
: repeated integer。显然有且只有一个重复的。用swap归位，如果 arr[arr[i]] ==
: arr[i]，就返回arr[i]。
: 这个问题问the first repeated integer，所以用一个变量存repeated integer seen
: so far，每次遇到新的就和这个比较一下。
|
r*********n
发帖数: 4553 | 27 没有关系啊，因为是归位，
比如第一次遇到
arr[i] = 3， arr[arr[i]] = 3，那么repeated number seen so far就是3
如果后面来一个
arr[j] = 10, arr[arr[j]] = 10, 那么10和3比较，还是存3
【在 j*****y 的大作中提到】
: 关键是怎么比较，因为那个应该是第一个 repeat number的数或许交换到后面去了
:
: the
: seen
|
j*****y
发帖数: 1071 | 28 能写一个 code 吗 ? thanks.
【在 r*********n 的大作中提到】
: 没有关系啊，因为是归位，
: 比如第一次遇到
: arr[i] = 3， arr[arr[i]] = 3，那么repeated number seen so far就是3
: 如果后面来一个
: arr[j] = 10, arr[arr[j]] = 10, 那么10和3比较，还是存3
|
j*****y
发帖数: 1071 | 29 你的算法应该是对的，不过挺难想到的，厉害
【在 b*******e 的大作中提到】
: example: { 3, 2, 4, 1 3} 3 is the fist repeated.
: // const space
: for (int i = 0; i < N; i++) {
: int x = a[i];
: if ( x> 0 ) {
: if ( a[x] < 0 ) { // means the xith item has been changed before.
: that means X has shown up already
: cout << x << endl;
: break;
: }
|
r*********n
发帖数: 4553 | 30 int tmp = numeric_limits::max();
for(int i = 0; i
while(arr[i] != arr[arr[i]])
swap(arr[i],arr[arr[i]]);
if(arr[i] == i) continue;
if(arr[i] < tmp ) tmp = arr[i];
}
试了一下
1 2 2 1 输出 1
4 2 2 4 1 输出 2
【在 j*****y 的大作中提到】
: 能写一个 code 吗 ? thanks.
|
|
|
b*******e
发帖数: 217 | 31 for 1221 the first repeated one is 2, not 1.
【在 r*********n 的大作中提到】
: int tmp = numeric_limits::max();
: for(int i = 0; i: while(arr[i] != arr[arr[i]])
: swap(arr[i],arr[arr[i]]);
: if(arr[i] == i) continue;
: if(arr[i] < tmp ) tmp = arr[i];
: }
: 试了一下
: 1 2 2 1 输出 1
: 4 2 2 4 1 输出 2
|
r*********n
发帖数: 4553 | 32 恩，我理解错了，没那么简单
【在 b*******e 的大作中提到】
: for 1221 the first repeated one is 2, not 1.
|
