V*****i 发帖数: 92 | 1 I cannot figure it out till now. Looking for help.
Given an array of integers with duplication, write a function to determine
whether this array is a sequence. A sequence is defined as every integer
between min and max is present. For example, {2, 3, 2, 5, 7, 7, 6, 4, 2} is
a sequence. But {2, 3, 5, 3} is not.
Write a program with O(n) time complexity, and O(1) space. The array CAN BE
DESTROYED. | f*******t 发帖数: 7549 | | x*****o 发帖数: 23 | 3 这个可以有。。。关键词, data can be DESTROYED...
那原来那个数组就可以用来存, 相当于你有O(N)的space了。
扫描数组两便就好了。
【在 f*******t 的大作中提到】 : 有可能吗。。
| n*******w 发帖数: 687 | 4 basic idea is to sort the array in O(n)
first, find minimal and maximal value, say min, max
if it is a sequence, after sorting, a[i] should store min+i, for i from 0 to
max-min
the code to sort in O(n),
for(i = 0 to n-1)
while(a[a[i]-min]!=a[i]){
swap(a, a[i]-min, i); //swap the element at the index (a[i]-min) and i
}
is
BE
【在 V*****i 的大作中提到】 : I cannot figure it out till now. Looking for help. : Given an array of integers with duplication, write a function to determine : whether this array is a sequence. A sequence is defined as every integer : between min and max is present. For example, {2, 3, 2, 5, 7, 7, 6, 4, 2} is : a sequence. But {2, 3, 5, 3} is not. : Write a program with O(n) time complexity, and O(1) space. The array CAN BE : DESTROYED.
| z*****n 发帖数: 447 | 5 有duplication,a[i] 不一定 store min+i
to
and i
【在 n*******w 的大作中提到】 : basic idea is to sort the array in O(n) : first, find minimal and maximal value, say min, max : if it is a sequence, after sorting, a[i] should store min+i, for i from 0 to : max-min : the code to sort in O(n), : for(i = 0 to n-1) : while(a[a[i]-min]!=a[i]){ : swap(a, a[i]-min, i); //swap the element at the index (a[i]-min) and i : } :
| V*****i 发帖数: 92 | 6 I use nooneknow's idea to write a program, it seems to be correct after many
testing, but I have not convinced myself yet using a clear logic. Anybody
can help?
bool if_sequence(int* a, int N) {
int min = a[0];
int max = a[0];
for (int i=1; i
if (a[i] < min) min = a[i];
else if (a[i] > max) max = a[i];
}
if (max-min+1 > N) return false;
// p is the pointer for the garbage area
int p = max-min+1;
for (int i=0; i
while (a[i] != min+i) {
if (a[i] != a[a[i]-min]) swap(a[i], a[a[i]-min]);
else if (p >= N) return false;
else swap(a[i], a[p++]);
}
}
return true;
}
【在 z*****n 的大作中提到】 : 有duplication,a[i] 不一定 store min+i : : to : and i
| q****x 发帖数: 7404 | 7 没看懂。到底什么是sequence?为何第一个是,第二个不是?
is
BE
【在 V*****i 的大作中提到】 : I cannot figure it out till now. Looking for help. : Given an array of integers with duplication, write a function to determine : whether this array is a sequence. A sequence is defined as every integer : between min and max is present. For example, {2, 3, 2, 5, 7, 7, 6, 4, 2} is : a sequence. But {2, 3, 5, 3} is not. : Write a program with O(n) time complexity, and O(1) space. The array CAN BE : DESTROYED.
| n*******w 发帖数: 687 | 8 本质上就是把a[i]放到它该待着的地方,如果那个地方已经store这个数了。不用swap
,直接i++处理下一个。
证明很容易,每次swap至少保证把一个元素放到该去的地方,最多n个不同的元素。最
多swap n次。
不过你这code好像会死循环。逻辑也不清晰。好像跟我说的有点反着的意思。
我觉得先sort完,再检查min到max中间每个元素是不是都存在,逻辑会比较清晰。
many
【在 V*****i 的大作中提到】 : I use nooneknow's idea to write a program, it seems to be correct after many : testing, but I have not convinced myself yet using a clear logic. Anybody : can help? : bool if_sequence(int* a, int N) { : int min = a[0]; : int max = a[0]; : for (int i=1; i: if (a[i] < min) min = a[i]; : else if (a[i] > max) max = a[i]; : }
|
| r*******n 发帖数: 3020 | 9 我也没看懂, 有没有人给翻译下
【在 q****x 的大作中提到】 : 没看懂。到底什么是sequence?为何第一个是,第二个不是? : : is : BE
| V*****i 发帖数: 92 | 10 抱歉,说的不是很清楚。这题是问一个数组,是不是最大值和最小值之间的每一个整数
都存在。比方说第一个数组,最小最大是2,7,数组中3,4,5,6都有,所以他是一个序列
。第二个数组中,缺4,所以不是序列。 | | | l*****n 发帖数: 577 | 11 Assume that the number range is smaller than half of possible range of the
data type, saying int. Then use the original array as hashtable to memorize
whether a number is in the arrey or not.
Modify Viterbi code below (not for easy typing, the idea behind is quite
different):
bool IsSequence(int* a, int N) {
int min = 0, max = 0;
for (int i=0; i
if (a[i] < min) min = a[i];
else if (a[i] > max) max = a[i];
}
if (max-min+1 > N) return false;
for (int i=0; i
for (int i=0; i
{
a[a[i]] = a[a[i]] * -1;
}
for(int i=0; i<=max-min; i++)
{
if(a[i] >= 0)return false;
}
return true;
}
Code not tested, just to show the idea.
many
【在 V*****i 的大作中提到】 : I use nooneknow's idea to write a program, it seems to be correct after many : testing, but I have not convinced myself yet using a clear logic. Anybody : can help? : bool if_sequence(int* a, int N) { : int min = a[0]; : int max = a[0]; : for (int i=1; i: if (a[i] < min) min = a[i]; : else if (a[i] > max) max = a[i]; : }
| s******e 发帖数: 114 | 12 no swap method,
first scan to get min and max
in second scan, each element minus min, then get an index array, 0,1,2,4,3,3
in 3rd scan, b = abs(a[i]);
if(a[b] >0) a[b] *= -1;
in 4th scan to find out if the all first max element are < 0;
2nd scan and 3rd scan can be merged. | e***s 发帖数: 799 | 13 赞CODE.这个a[a[i]] *= -1;太巧了!
the
memorize
quite
【在 l*****n 的大作中提到】 : Assume that the number range is smaller than half of possible range of the : data type, saying int. Then use the original array as hashtable to memorize : whether a number is in the arrey or not. : Modify Viterbi code below (not for easy typing, the idea behind is quite : different): : bool IsSequence(int* a, int N) { : int min = 0, max = 0; : for (int i=0; i: if (a[i] < min) min = a[i]; : else if (a[i] > max) max = a[i];
| d****n 发帖数: 233 | 14 My implementation of sdvaline' idea:
boolean isSquence(int[] a, int N) {
int min = a[0];
int max = a[0];
// first scan
for (int i = 0; i < N; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}
// return if there are not enough elements to form a sequence
if (max - min + 1 > N) {
return false;
}
// second scan
for (int i = 0; i < N; i++) {
a[i] -= min;
}
// third scan
for (int i = 0; i < N; i++) {
int index = Math.abs(a[i]);
a[index] = (a[index] < 0)? a[index] : -1 * a[index];
}
// fourth scan
for (int i = 0; i < max - min + 1; i++) {
if (a[i] > 0) {
return false;
}
}
return true;
} | d*******l 发帖数: 338 | 15 你这个和楼上那个思路并不一样,初看有点怪,看明白之后觉得应该是对的,而且还挺
巧的。比楼上的其它方法更直接。很难想象你自己没弄明白能写出来。。
many
【在 V*****i 的大作中提到】 : I use nooneknow's idea to write a program, it seems to be correct after many : testing, but I have not convinced myself yet using a clear logic. Anybody : can help? : bool if_sequence(int* a, int N) { : int min = a[0]; : int max = a[0]; : for (int i=1; i: if (a[i] < min) min = a[i]; : else if (a[i] > max) max = a[i]; : }
| q****x 发帖数: 7404 | 16 O(N) time O(1) space应该能搞定。
【在 V*****i 的大作中提到】 : 抱歉,说的不是很清楚。这题是问一个数组,是不是最大值和最小值之间的每一个整数 : 都存在。比方说第一个数组,最小最大是2,7,数组中3,4,5,6都有,所以他是一个序列 : 。第二个数组中,缺4,所以不是序列。
| c*****e 发帖数: 3226 | 17 关键是借助-1把数字做个标记下来,有的脑筋急转弯。
,3
【在 s******e 的大作中提到】 : no swap method, : first scan to get min and max : in second scan, each element minus min, then get an index array, 0,1,2,4,3,3 : in 3rd scan, b = abs(a[i]); : if(a[b] >0) a[b] *= -1; : in 4th scan to find out if the all first max element are < 0; : 2nd scan and 3rd scan can be merged.
| n*******w 发帖数: 687 | 18 那个思路的确够曲折的。看了半天发现的确work。
sdvaline 的code有个bug。第4个scan判断的时候应该是要把0当做valid,这个没问题。
但是0是valid的话,会出现问题。如果数组里存在多个min。
反例比如[0 0 2],答案是false,但是跑出来的结果是true。
0要特殊对待。
【在 d*******l 的大作中提到】 : 你这个和楼上那个思路并不一样,初看有点怪,看明白之后觉得应该是对的,而且还挺 : 巧的。比楼上的其它方法更直接。很难想象你自己没弄明白能写出来。。 : : many
| s******e 发帖数: 114 | 19 Yes. you are right. that is a bug. I managed to use two scans.
since array can be destroyed, so we can modify the value to make a flag, say
the original value is x, flaged value is x + (max-min+1).
// first scan skiped to get min and max
// second scan;
count = 0;
for(int i=0;i< n;i++)
{
//restore to original value
if(a[i] > max)
{
value = a[i] - max;
}
else
{
value = a[i];
}
//index
index = value - min;
if(a[index] < = max)
{
count ++;
a[index] += (max -min +1);
}
}
return count == max -min +1;
题。
【在 n*******w 的大作中提到】 : 那个思路的确够曲折的。看了半天发现的确work。 : sdvaline 的code有个bug。第4个scan判断的时候应该是要把0当做valid,这个没问题。 : 但是0是valid的话,会出现问题。如果数组里存在多个min。 : 反例比如[0 0 2],答案是false,但是跑出来的结果是true。 : 0要特殊对待。
| a*****t 发帖数: 30 | 20 这个不错。
就有一点:
下面这一行是不是要改成 value = a[i] - (max - min + 1),
还是我理解错了?
//restore to original value
if(a[i] > max)
{
value = a[i] - max; <-------------
}
say
【在 s******e 的大作中提到】 : Yes. you are right. that is a bug. I managed to use two scans. : since array can be destroyed, so we can modify the value to make a flag, say : the original value is x, flaged value is x + (max-min+1). : // first scan skiped to get min and max : // second scan; : count = 0; : for(int i=0;i< n;i++) : { : //restore to original value : if(a[i] > max)
| | | v****1 发帖数: 12 | 21 没看明白,大虾给解释解释?
【在 d*******l 的大作中提到】 : 你这个和楼上那个思路并不一样,初看有点怪,看明白之后觉得应该是对的,而且还挺 : 巧的。比楼上的其它方法更直接。很难想象你自己没弄明白能写出来。。 : : many
| h******l 发帖数: 254 | 22 zan,终于有个明白的解释了
,3
【在 s******e 的大作中提到】 : no swap method, : first scan to get min and max : in second scan, each element minus min, then get an index array, 0,1,2,4,3,3 : in 3rd scan, b = abs(a[i]); : if(a[b] >0) a[b] *= -1; : in 4th scan to find out if the all first max element are < 0; : 2nd scan and 3rd scan can be merged.
| d*******l 发帖数: 338 | 23 不敢。我说说我的想法:一般的思路先找min和max肯定没问题,接下来的做法通常就是
对i从0-n-1,不断把a[i]换到a[a[i]-min]去,直到a[i]=a[a[i]-min]。然后再从头检
查一遍前max-min+1个元素是不是满足a[i]=i+min就行。
但他的那个方法是i只从0循环到max-min,并且检测到a[i]=a[a[i]-min]并不停止,而
是把后面的换过来继续做交换。如果观察他的程序,可以看出p只有在出现了duplicate
之后才可能++。p初始是max-min+1,说明我们至少需要max-min+1个不同元素来构成
sequence,每出现一个duplicate,p++。如果p=N就说明我们需要N个元素才可能构成序
列,这个时候如果再碰到duplicate就说明无法取到max-min+1个不同元素了,因为
duplicates的数量超过了可以接受的最大值。
【在 v****1 的大作中提到】 : 没看明白,大虾给解释解释?
| v****1 发帖数: 12 | 24 多谢,我理解是把序列的前max-min+1项变成a[i]=i+min,不过怎么想到通过交换a[i]和
a[a[i]-min]这种方式的?
duplicate
【在 d*******l 的大作中提到】 : 不敢。我说说我的想法:一般的思路先找min和max肯定没问题,接下来的做法通常就是 : 对i从0-n-1,不断把a[i]换到a[a[i]-min]去,直到a[i]=a[a[i]-min]。然后再从头检 : 查一遍前max-min+1个元素是不是满足a[i]=i+min就行。 : 但他的那个方法是i只从0循环到max-min,并且检测到a[i]=a[a[i]-min]并不停止,而 : 是把后面的换过来继续做交换。如果观察他的程序,可以看出p只有在出现了duplicate : 之后才可能++。p初始是max-min+1,说明我们至少需要max-min+1个不同元素来构成 : sequence,每出现一个duplicate,p++。如果p=N就说明我们需要N个元素才可能构成序 : 列,这个时候如果再碰到duplicate就说明无法取到max-min+1个不同元素了,因为 : duplicates的数量超过了可以接受的最大值。
| d*******l 发帖数: 338 | 25 把a[i]换到a[a[i]-min]其实就是在把a[j]变成j+min的过程,j=a[i]-min。
【在 v****1 的大作中提到】 : 多谢,我理解是把序列的前max-min+1项变成a[i]=i+min,不过怎么想到通过交换a[i]和 : a[a[i]-min]这种方式的? : : duplicate
| s*****k 发帖数: 18 | 26 这个是不对的,试试{ 3, 3, 2, 1, 0, 5, 1, 2 }
可以用一个tail记录最后一个index,然后不停地把当前的数字放到应该放的位置上,
如果应该放的位置已经有数字了,就和tail交换,然后tail--。
当当前的数字应该在的位置超过tail时,return false。
当循环到tail的时候,循环结束。
然后最后检查0->tail的位置是不是一个序列。
【在 d****n 的大作中提到】 : My implementation of sdvaline' idea: : boolean isSquence(int[] a, int N) { : int min = a[0]; : int max = a[0]; : : // first scan : for (int i = 0; i < N; i++) { : if (a[i] < min) { : min = a[i]; : }
| v****1 发帖数: 12 | 27 十分感谢。 现在是把a[i]换到a[a[i]-min]去,如果反过来把a[i]-min换到a[i]呢?这
样最后一遍扫描也不用了.
【在 d*******l 的大作中提到】 : 把a[i]换到a[a[i]-min]其实就是在把a[j]变成j+min的过程,j=a[i]-min。
| d****n 发帖数: 233 | 28 // this one is similar to v1 but in third scan, it count the # of uniq
elements
boolean isSquence_v2(int[] a, int N) {
int min = a[0];
int max = a[0];
// first scan
for (int i = 0; i < N; i++) {
if (a[i] < min) {
min = a[i];
}
else if (a[i] > max) {
max = a[i];
}
}
// return if there are not enough elements to form a sequence
if (max - min + 1 > N) {
return false;
}
// second scan
for (int i = 0; i < N; i++) {
a[i] = a[i] - min + 1; // make the least value to be 1 instead
of 0 to avoid ambiguous later.
}
int count = 0;
// third scan
for (int i = 0; i < N; i++) {
int index = Math.abs(a[i]) - 1; // -1 because we added 1 earlier.
if (a[index] > 0) { ++count; a[index] *= -1;}
}
return count == max - min + 1;
}
【在 s*****k 的大作中提到】 : 这个是不对的,试试{ 3, 3, 2, 1, 0, 5, 1, 2 } : 可以用一个tail记录最后一个index,然后不停地把当前的数字放到应该放的位置上, : 如果应该放的位置已经有数字了,就和tail交换,然后tail--。 : 当当前的数字应该在的位置超过tail时,return false。 : 当循环到tail的时候,循环结束。 : 然后最后检查0->tail的位置是不是一个序列。
| n*******w 发帖数: 687 | 29 a[i]-min换到a[i]的逻辑稍复杂一些。
面试一紧张不一定玩得转,个人觉得。
【在 v****1 的大作中提到】 : 十分感谢。 现在是把a[i]换到a[a[i]-min]去,如果反过来把a[i]-min换到a[i]呢?这 : 样最后一遍扫描也不用了.
| r*******g 发帖数: 1335 | 30 你一边说没看懂一边写出这么好的解法,牛
这个关键似乎是:p之后的数字无所谓,只要前面1到max-min+1的位置都找到了就好。
many
【在 V*****i 的大作中提到】 : I use nooneknow's idea to write a program, it seems to be correct after many : testing, but I have not convinced myself yet using a clear logic. Anybody : can help? : bool if_sequence(int* a, int N) { : int min = a[0]; : int max = a[0]; : for (int i=1; i: if (a[i] < min) min = a[i]; : else if (a[i] > max) max = a[i]; : }
| | | r*******g 发帖数: 1335 | 31 你一边说没看懂一边写出这么好的解法,牛
这个关键似乎是:p之后的数字无所谓,只要前面1到max-min+1的位置都找到了就好。
many
【在 V*****i 的大作中提到】 : I use nooneknow's idea to write a program, it seems to be correct after many : testing, but I have not convinced myself yet using a clear logic. Anybody : can help? : bool if_sequence(int* a, int N) { : int min = a[0]; : int max = a[0]; : for (int i=1; i: if (a[i] < min) min = a[i]; : else if (a[i] > max) max = a[i]; : }
| p*****2 发帖数: 21240 | 32 2, 3, 2, 5, 7, 7, 6, 4, 2
先扫一遍得到最小最大值
min=2
max=7
在扫一遍把每个数减去最小值
0,1,0,3,5,5,4,2,0
在扫一遍,把每个数放到这个数的index上,比如,0,放到index 0。如果有duplicate
不管。
0, 1, 2, 3, 4, 5, 2, 0
这样,前边max-min+1个数应该出现,0-max-min+1才对。否则,就return false. |
|