B*******1
发帖数: 2454 | 1 Given an int array which might contain duplicates, find if it is a sequence.
Eg. {45,50,47,46,49,48}
is a sequence 46,47,48,49,50
Sorting is an obvious solution. Can this be done in O(n) time and O(1) space |
y*******g
发帖数: 6599 | 2 不懂，有duplicate还算sequence吗？ |
A**u
发帖数: 2458 | 3 这可能有O(1) O(n)的?
sequence.
space
【在 B*******1 的大作中提到】
: Given an int array which might contain duplicates, find if it is a sequence.
: Eg. {45,50,47,46,49,48}
: is a sequence 46,47,48,49,50
: Sorting is an obvious solution. Can this be done in O(n) time and O(1) space
|
B*******1
发帖数: 2454 | 4 应该不算。
【在 y*******g 的大作中提到】
: 不懂，有duplicate还算sequence吗？
|
c****p
发帖数: 6474 | 5 are mathematical methods possible?
1. max - min == n - 1; // not able to deal with duplicates.
2. check with sum(a[i]) and sum(a[i]^2); // any possible exceptions?
3. xor; // easy to get a false positive.
combine 1 & 2 together might be feasible but not sure whether they work for
all the corner cases.
sequence.
space
【在 B*******1 的大作中提到】
: Given an int array which might contain duplicates, find if it is a sequence.
: Eg. {45,50,47,46,49,48}
: is a sequence 46,47,48,49,50
: Sorting is an obvious solution. Can this be done in O(n) time and O(1) space
|
v*****k
发帖数: 7798 | |
b*******y
发帖数: 232 | 7 这个好像有点难度，第二个的exception应该比较多，特别是元素个数非常多的情况下。
例如，-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6
和 -6,-5,-5,0,-2,-1,0,1,2,0,5,5,6
用了5^2 = 4^2 + 3^2
for
【在 c****p 的大作中提到】
: are mathematical methods possible?
: 1. max - min == n - 1; // not able to deal with duplicates.
: 2. check with sum(a[i]) and sum(a[i]^2); // any possible exceptions?
: 3. xor; // easy to get a false positive.
: combine 1 & 2 together might be feasible but not sure whether they work for
: all the corner cases.
:
: sequence.
: space
|
B*******1
发帖数: 2454 | |
a***y
发帖数: 547 | 9 say array A find the max and min,
then find a way to put min at A[0], max at A[n-1] and so on in O(n) time.
sequence.
space
【在 B*******1 的大作中提到】
: Given an int array which might contain duplicates, find if it is a sequence.
: Eg. {45,50,47,46,49,48}
: is a sequence 46,47,48,49,50
: Sorting is an obvious solution. Can this be done in O(n) time and O(1) space
|
c****p
发帖数: 6474 | 10 这个不错
【在 a***y 的大作中提到】
: say array A find the max and min,
: then find a way to put min at A[0], max at A[n-1] and so on in O(n) time.
:
: sequence.
: space
|
|
|
D*******e
发帖数: 151 | 11 It's not O(n). It's O(n^2)
【在 a***y 的大作中提到】
: say array A find the max and min,
: then find a way to put min at A[0], max at A[n-1] and so on in O(n) time.
:
: sequence.
: space
|
c****p
发帖数: 6474 | 12 应该是这样，先把min和max分别放在A[0]，A[n-1]，
然后对于A[i]，且A[i]-min != i，则将其和A[A[i]-min]换，如果A[A[i]-min]==A[i]，
那就fail了（有重复的）。
换完之后再扫一遍，如果有A[i] != i+min的就fail，否则就成功。
【在 a***y 的大作中提到】
: say array A find the max and min,
: then find a way to put min at A[0], max at A[n-1] and so on in O(n) time.
:
: sequence.
: space
|
y*******g
发帖数: 6599 | 13 扫一遍找到最大和最小 O(n)
如果最大最小只差不是 size-1, false
如果是size-1， 则有两种情况，有重复，和sequence，
这样就转化成了这道题目：
http://www.mitbbs.com/article_t/JobHunting/31947559.html
用linkedlist找loop的方法， O(n) |
B*******1
发帖数: 2454 | 14 thanks，那个帖子里面最后那个dead loop怎么解决啊？
【在 y*******g 的大作中提到】
: 扫一遍找到最大和最小 O(n)
: 如果最大最小只差不是 size-1, false
: 如果是size-1， 则有两种情况，有重复，和sequence，
: 这样就转化成了这道题目：
: http://www.mitbbs.com/article_t/JobHunting/31947559.html
: 用linkedlist找loop的方法， O(n)
|
D*******e
发帖数: 151 | 15 I think this is correct.
]，
【在 c****p 的大作中提到】
: 应该是这样，先把min和max分别放在A[0]，A[n-1]，
: 然后对于A[i]，且A[i]-min != i，则将其和A[A[i]-min]换，如果A[A[i]-min]==A[i]，
: 那就fail了（有重复的）。
: 换完之后再扫一遍，如果有A[i] != i+min的就fail，否则就成功。
|
A**u
发帖数: 2458 | 16 我的神哪
你砸想到的
我看的下标都晕了
]，
【在 c****p 的大作中提到】
: 应该是这样，先把min和max分别放在A[0]，A[n-1]，
: 然后对于A[i]，且A[i]-min != i，则将其和A[A[i]-min]换，如果A[A[i]-min]==A[i]，
: 那就fail了（有重复的）。
: 换完之后再扫一遍，如果有A[i] != i+min的就fail，否则就成功。
|
c****p
发帖数: 6474 | 17 和找0~n-1中缺失的元素的算法一样。
【在 A**u 的大作中提到】
: 我的神哪
: 你砸想到的
: 我看的下标都晕了
:
: ]，
|
A**u
发帖数: 2458 | 18 大牛 0~n-1缺失算法，详细题目是什么， 我考古一下。
新手，不懂...
【在 c****p 的大作中提到】
: 和找0~n-1中缺失的元素的算法一样。
|
C***U
发帖数: 2406 | 19 introduction to algorithm里面的练习题.
【在 A**u 的大作中提到】
: 大牛 0~n-1缺失算法，详细题目是什么， 我考古一下。
: 新手，不懂...
|
m**q
发帖数: 189 | 20 我觉得这道题和那题不一样。
这道题就是grass以前说过的把value i放到位置i的变形。
你说的那个check cycle的方法有一个限制条件是
index 0~n-1, value 1~n-1，才能保证找到dup。
在这个题的条件下不满足。我刚刚在那道题的链接里更新了
http://www.mitbbs.com/mitbbs_bbsccc.php?board=JobHunting&file=M
【在 y*******g 的大作中提到】
: 扫一遍找到最大和最小 O(n)
: 如果最大最小只差不是 size-1, false
: 如果是size-1， 则有两种情况，有重复，和sequence，
: 这样就转化成了这道题目：
: http://www.mitbbs.com/article_t/JobHunting/31947559.html
: 用linkedlist找loop的方法， O(n)
|
|
|
C***U
发帖数: 2406 | 21 great!
]，
【在 c****p 的大作中提到】
: 应该是这样，先把min和max分别放在A[0]，A[n-1]，
: 然后对于A[i]，且A[i]-min != i，则将其和A[A[i]-min]换，如果A[A[i]-min]==A[i]，
: 那就fail了（有重复的）。
: 换完之后再扫一遍，如果有A[i] != i+min的就fail，否则就成功。
|
A**u
发帖数: 2458 | 22 是这个吗
数组A中包含n-1个[0,n-1]内的不同整数，n个数中只有一个数不在所给的数组中。设计
一个找到这个数的O(n)时间的算法
这个算法不是 用异或吗 和这个题目有关系？
【在 C***U 的大作中提到】
: introduction to algorithm里面的练习题.
|
C*******l
发帖数: 1198 | 23 如果是O(n) time O(n) space完全是trivial。 |
y*******g
发帖数: 6599 | 24 当然一样啊，
我已经check过了 max和min，当然要直接套的话需要把每个value都减去min-1
【在 m**q 的大作中提到】
: 我觉得这道题和那题不一样。
: 这道题就是grass以前说过的把value i放到位置i的变形。
: 你说的那个check cycle的方法有一个限制条件是
: index 0~n-1, value 1~n-1，才能保证找到dup。
: 在这个题的条件下不满足。我刚刚在那道题的链接里更新了
: http://www.mitbbs.com/mitbbs_bbsccc.php?board=JobHunting&file=M
|
m**q
发帖数: 189 | 25 那个题的限制条件是 n个数，n-1个取值，所以可以用
check cycle的方法。
这道题不满足上述条件，举个例子：
index 0 1 2 3 4
value 4 2 2 3 0
min是0，max是4，max-min=4
check cycle的方法只能找到 0，4两个元素
构成的环，无法发现2是dup
【在 y*******g 的大作中提到】
: 当然一样啊，
: 我已经check过了 max和min，当然要直接套的话需要把每个value都减去min-1
|
Z**********4
发帖数: 528 | 26 如果最大跟最小的差小于size-1不一定是false啊。比如
11111123应该也算是sequence吧 因为原题是允许duplicates的。
【在 y*******g 的大作中提到】
: 扫一遍找到最大和最小 O(n)
: 如果最大最小只差不是 size-1, false
: 如果是size-1， 则有两种情况，有重复，和sequence，
: 这样就转化成了这道题目：
: http://www.mitbbs.com/article_t/JobHunting/31947559.html
: 用linkedlist找loop的方法， O(n)
|
Z**********4
发帖数: 528 | 27 问题是题目中说允许重复的呀
比如
11123
应该返回true吧？但是按照你的算法返回的是false
]，
【在 c****p 的大作中提到】
: 应该是这样，先把min和max分别放在A[0]，A[n-1]，
: 然后对于A[i]，且A[i]-min != i，则将其和A[A[i]-min]换，如果A[A[i]-min]==A[i]，
: 那就fail了（有重复的）。
: 换完之后再扫一遍，如果有A[i] != i+min的就fail，否则就成功。
|
c****p
发帖数: 6474 | 28 99699
【在 Z**********4 的大作中提到】
: 问题是题目中说允许重复的呀
: 比如
: 11123
: 应该返回true吧？但是按照你的算法返回的是false
:
: ]，
|
c****p
发帖数: 6474 | 29 那把我的算法小改一下就可以了。
【在 Z**********4 的大作中提到】
: 问题是题目中说允许重复的呀
: 比如
: 11123
: 应该返回true吧？但是按照你的算法返回的是false
:
: ]，
|
y*******g
发帖数: 6599 | 30 明白了
【在 m**q 的大作中提到】
: 那个题的限制条件是 n个数，n-1个取值，所以可以用
: check cycle的方法。
: 这道题不满足上述条件，举个例子：
: index 0 1 2 3 4
: value 4 2 2 3 0
: min是0，max是4，max-min=4
: check cycle的方法只能找到 0，4两个元素
: 构成的环，无法发现2是dup
|
|
|
k****n
发帖数: 369 | 31 find min and max, then swap to right position
sequence.
space
【在 B*******1 的大作中提到】
: Given an int array which might contain duplicates, find if it is a sequence.
: Eg. {45,50,47,46,49,48}
: is a sequence 46,47,48,49,50
: Sorting is an obvious solution. Can this be done in O(n) time and O(1) space
|
Y**B
发帖数: 144 | 32 wrong
]，
【在 c****p 的大作中提到】
: 应该是这样，先把min和max分别放在A[0]，A[n-1]，
: 然后对于A[i]，且A[i]-min != i，则将其和A[A[i]-min]换，如果A[A[i]-min]==A[i]，
: 那就fail了（有重复的）。
: 换完之后再扫一遍，如果有A[i] != i+min的就fail，否则就成功。
|
b******g
发帖数: 1721 | 33 刚才写了一堆，结果网页给没了，太郁闷了。好吧，我的思路如下：
扫一遍得到最小值，
扫一遍使得数组中每个元素减去最小值，
再扫一遍得到总和，sum，
判断sum=k(k-1)/2, where k =数组的长度，
if true, then a sequence,
else, not a sequence. |
c****p
发帖数: 6474 | 34 1 2 2 5 5 6 7
【在 b******g 的大作中提到】
: 刚才写了一堆，结果网页给没了，太郁闷了。好吧，我的思路如下：
: 扫一遍得到最小值，
: 扫一遍使得数组中每个元素减去最小值，
: 再扫一遍得到总和，sum，
: 判断sum=k(k-1)/2, where k =数组的长度，
: if true, then a sequence,
: else, not a sequence.
|
b******g
发帖数: 1721 | 35 好吧，我没考虑到有多个repeated 的数字的时候，有这个巧合的情况。
1 2 2 5 5 6 7
【在 b******g 的大作中提到】
: 刚才写了一堆，结果网页给没了，太郁闷了。好吧，我的思路如下：
: 扫一遍得到最小值，
: 扫一遍使得数组中每个元素减去最小值，
: 再扫一遍得到总和，sum，
: 判断sum=k(k-1)/2, where k =数组的长度，
: if true, then a sequence,
: else, not a sequence.
|
u**r
发帖数: 663 | 36 只需要扫一遍，同时记录最小值，数组长度，summation，用等差数列求和公式验证之。
前提是出现重复的就不算sequance.
【在 b******g 的大作中提到】
: 刚才写了一堆，结果网页给没了，太郁闷了。好吧，我的思路如下：
: 扫一遍得到最小值，
: 扫一遍使得数组中每个元素减去最小值，
: 再扫一遍得到总和，sum，
: 判断sum=k(k-1)/2, where k =数组的长度，
: if true, then a sequence,
: else, not a sequence.
|
