i**d
发帖数: 357 | 1 you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
只能想到brute force的方法。有什么好的办法来做么？
谢谢了。 | m********l
发帖数: 4394 | 2 why not put it in a hash first
then get rid of those that has no neighbor,
then get the max sequence.
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| d*******l
发帖数: 338 | 3 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| b*****c
发帖数: 1103 | 4 n log(n) 的算法能否详细说说，我看不明白，谢谢
【在 d*******l 的大作中提到】
: 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
: subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
:
: .:
| g**********y
发帖数: 14569 | 5 这个题在本版问过，这是当时给的解，去考古一下吧
public class LongestRange {
public int[] longest(int[] a) {
int start = 0;
int maxLen = 0;
HashMap map = new HashMap();
for (int i=0; i
int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
int len = left + 1 + right;
map.put(a[i]-left, len);
map.put(a[i]+right, len);
if (len > maxLen) {
maxLen = len;
start = a[i] - left;
}
}
int[] b = new int[maxLen];
for (int i=0; i
return b;
}
} | H****s
发帖数: 247 | | b*****c
发帖数: 1103 | 7 这是允许不连续的subarray, 问问楼主是不是想问contiguous subarray?
【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
| b*****c
发帖数: 1103 | 8 题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567 | m********l
发帖数: 4394 | 9 嗯。。。
刚才我也看错了
【在 b*****c 的大作中提到】
: 题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567
| d*******l
发帖数: 338 | 10 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。
【在 b*****c 的大作中提到】
: n log(n) 的算法能否详细说说，我看不明白，谢谢
| | | m********l
发帖数: 4394 | 11 a = {4,5,1,5,7,4,3,6,9,8,9}
这个你怎么测？
你还是要O(N^2)吧
Dynamic Programming从后面开始应该O(n)吧
l
【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
| b*****c
发帖数: 1103 | 12 貌似长度l无法二分吧。。。。
5,7,4,3,6
不存在长度4的窗口，但有窗口5。。
l
【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
| d*******l
发帖数: 338 | 13 我也发现了这个问题。。还是得从大到小。n^2
【在 b*****c 的大作中提到】
: 貌似长度l无法二分吧。。。。
: 5,7,4,3,6
: 不存在长度4的窗口，但有窗口5。。
:
: l
| d*******l
发帖数: 338 | 14 这题dp怎么弄？好像不存在递推关系
【在 m********l 的大作中提到】
: a = {4,5,1,5,7,4,3,6,9,8,9}
: 这个你怎么测？
: 你还是要O(N^2)吧
: Dynamic Programming从后面开始应该O(n)吧
:
: l
| g**********y
发帖数: 14569 | 15 别，这不是我解的，我只是记下了当时大家讨论的最佳解。
【在 H****s 的大作中提到】
: 火鸡，还是你牛！PF
| m********l
发帖数: 4394 | 16 我觉的这个主要是要知道什么时候该停
- keep track of remaining length
- keep track of average or sum of remaining elements.
if the difference between current number and subsequent numbers exceed a
threshold (stored), then stop
go to the next number.
【在 d*******l 的大作中提到】
: 这题dp怎么弄？好像不存在递推关系
| d*******l
发帖数: 338 | 17 这个就不是dp了吧。我觉得想做到严格O(n^2)以下还是挺困难的
【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
| b*****c
发帖数: 1103 | 18 我觉得反而怎么检测重复比较难
【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
| g***y
发帖数: 764 | 19 ido not understand this problem statement
can you please elaborate?
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| r*******g
发帖数: 1335 | 20 假设出现重复的数字，你是怎么处理的。
比如，1,2,2
到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
，不是么？
你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
选出一段不重复的可以组成sequence。
【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
| | | B*******1
发帖数: 2454 | | b*****c
发帖数: 1103 | 22 你就不看看我的回复么，呜呜
火鸡的算法是输出3，4，5，6，7的，不是5,7,4,3,6
【在 r*******g 的大作中提到】
: 假设出现重复的数字，你是怎么处理的。
: 比如，1,2,2
: 到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
: 因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
: ，不是么？
: 你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
: 选出一段不重复的可以组成sequence。
| r*******g
发帖数: 1335 | 23 还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
1的序列。
【在 B*******1 的大作中提到】
: 火鸡的代码似乎漏了检测重复，原帖子在这里
: http://www.mitbbs.com/article_t/JobHunting/31911013.html
: 作者的代码是有检测重复的。
| B*******1
发帖数: 2454 | 24 恩，的确有点不一样，但是似乎把连接里面的方法改进一下就可以得到这题的答案了。
【在 r*******g 的大作中提到】
: 还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
: 1的序列。
| s******e
发帖数: 108 | 25 This is harder question.
For example.
int []a =new int[] {4,5,1,5,7,4,3,6,3,1,9,8};
should return {5,7,4,3,6}
rather than {3,4,5,6,7,8,9} or {5,7,4,3,6,9,8}
because it needs to consider that
the index of the elements should also
need to satisfy the condition
of longest consecutive increase sequence.
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| s******e
发帖数: 108 | 26 A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;
int indexStart =0;
int indexMaxLen =0;
HashMap map = new HashMap();
HashMap indexmap = new HashMap();
for (int i=0; i
Node valNode = map.get(a[i]);
if(valNode==null){
Node newNode = new Node(1,i);
map.put(a[i], newNode);
indexmap.put(i, 1);
Node lowerValNode = map.get(a[i]-1);
if(lowerValNode!=null){
int newVal = lowerValNode.lenVal+1;
Node aiNode = map.get(a[i]);
aiNode.lenVal = newVal;
// map.put(a[i], newVal); //high part
Node startRangeNode = map.get(a[i]-newVal+1);
startRangeNode.lenVal = newVal;
// map.put(a[i]-newVal+1, newVal); //low part
if(newVal >maxLen){
maxLen = newVal;
start = a[i]-newVal+1;
}
//loop1, [a[i]-newVal+1, a[i]]
//check i-1
//check a[i-1] whether in loop1
if( (a[i-1]<=a[i]) && (a[i-1]>=a[i]-newVal+1) ){
//merge i with i-1 in the indexmap
Integer lowerIndexLenVal= indexmap.get(i-1);
int newIndexLenVal = lowerIndexLenVal+1;
indexmap.put(i, newIndexLenVal);
indexmap.put(i-newIndexLenVal+1, newIndexLenVal);
if(indexMaxLen < newIndexLenVal){
indexStart = i-newIndexLenVal+1;
indexMaxLen = newIndexLenVal;
}
}
}
Node highValNode = map.get(a[i]+1);
if(highValNode!=null){
int highVal = highValNode.lenVal;
Node aiNode = map.get(a[i]);
int newVal = aiNode.lenVal + highVal;
Node endRangeNode = map.get(a[i]+highVal);
endRangeNode.lenVal = newVal;
// map.put(a[i]+highValNode.lenVal, newVal);//high part
Node startRangeNode = map.get(a[i]+highVal-newVal+1);
startRangeNode.lenVal = newVal;
// map.put(a[i]+highVal-newVal+1, newVal); //low part
if(newVal >maxLen){
maxLen = newVal;
start = a[i]+highVal-newVal+1;
}
//loop1, [a[i]+highVal-newVal+1,a[i]+highVal]
//check
int p1 = highValNode.index;
Integer p1LenVal = indexmap.get(p1);
//range, [p1,p1+p1LenVal-1]
//check whether in loop1
if(a[p1+p1LenVal]>= a[i]+highVal-newVal+1 && a[p1+
p1LenVal]<= a[i]+highVal){
//merge loop2
Integer len1=indexmap.get(p1+p1LenVal);
int newLen1 = len1+p1LenVal;
indexmap.put(p1, newLen1);
indexmap.put(p1+newLen1-1, newLen1);
if(indexMaxLen < newLen1){
indexStart = p1;
indexMaxLen = newLen1;
}
}
if(a[p1-1]>= a[i]+highVal-newVal+1 && a[p1-1]<= a[i]+
highVal){
Integer len2=indexmap.get(p1-1);
Integer newp1LenVal = indexmap.get(p1);
int newLen2=len2+newp1LenVal;
indexmap.put(p1-len2, newLen2);
indexmap.put(p1-len2+newLen2-1, newLen2);
if(indexMaxLen < newLen2){
indexStart = p1-len2;
indexMaxLen = newLen2;
}
}
}
} else {
valNode.index=i;
indexmap.put(i, 1);
//more to be done
}
// Integer indexVal = indexmap.get(i);
// if(indexVal==null){
//
// }
}
int[] b = new int[maxLen];
for (int i=0; i
b[i] = start + i;
System.out.print(b[i]+" ");
}
System.out.println();
for(Integer key : map.keySet()) {
Integer val = map.get(key).lenVal;
System.out.println("key: "+key+ " val: "+ val);
}
int[] b2 = new int[indexMaxLen];
for (int i=0; i
b2[i] = indexStart + i;
System.out.print(a[b2[i]]+" ");
}
System.out.println();
return b;
}
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| i**d
发帖数: 357 | 27 you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
只能想到brute force的方法。有什么好的办法来做么？
谢谢了。 | m********l
发帖数: 4394 | 28 why not put it in a hash first
then get rid of those that has no neighbor,
then get the max sequence.
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| d*******l
发帖数: 338 | 29 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| b*****c
发帖数: 1103 | 30 n log(n) 的算法能否详细说说，我看不明白，谢谢
【在 d*******l 的大作中提到】
: 我能想到nlogn的办法，二分窗口的长度，对每个长度l检查是否有某个长为l的
: subarray满足条件，这个有点tricky但我觉得应该可以O(n)做到。
:
: .:
| | | g**********y
发帖数: 14569 | 31 这个题在本版问过，这是当时给的解，去考古一下吧
public class LongestRange {
public int[] longest(int[] a) {
int start = 0;
int maxLen = 0;
HashMap map = new HashMap();
for (int i=0; i
int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
int len = left + 1 + right;
map.put(a[i]-left, len);
map.put(a[i]+right, len);
if (len > maxLen) {
maxLen = len;
start = a[i] - left;
}
}
int[] b = new int[maxLen];
for (int i=0; i
return b;
}
} | H****s
发帖数: 247 | | b*****c
发帖数: 1103 | 33 这是允许不连续的subarray, 问问楼主是不是想问contiguous subarray?
【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
| b*****c
发帖数: 1103 | 34 题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567 | m********l
发帖数: 4394 | 35 嗯。。。
刚才我也看错了
【在 b*****c 的大作中提到】
: 题目要输出5,7,4,3,6，应该是指连续的吧，不连续的话输出34567
| d*******l
发帖数: 338 | 36 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。
【在 b*****c 的大作中提到】
: n log(n) 的算法能否详细说说，我看不明白，谢谢
| m********l
发帖数: 4394 | 37 a = {4,5,1,5,7,4,3,6,9,8,9}
这个你怎么测？
你还是要O(N^2)吧
Dynamic Programming从后面开始应该O(n)吧
l
【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
| b*****c
发帖数: 1103 | 38 貌似长度l无法二分吧。。。。
5,7,4,3,6
不存在长度4的窗口，但有窗口5。。
l
【在 d*******l 的大作中提到】
: 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
: 按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
: 列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
: 的满足条件的窗口。
: 对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
: 先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
: 口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
: 用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
: 个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
: 。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
| d*******l
发帖数: 338 | 39 我也发现了这个问题。。还是得从大到小。n^2
【在 b*****c 的大作中提到】
: 貌似长度l无法二分吧。。。。
: 5,7,4,3,6
: 不存在长度4的窗口，但有窗口5。。
:
: l
| d*******l
发帖数: 338 | 40 这题dp怎么弄？好像不存在递推关系
【在 m********l 的大作中提到】
: a = {4,5,1,5,7,4,3,6,9,8,9}
: 这个你怎么测？
: 你还是要O(N^2)吧
: Dynamic Programming从后面开始应该O(n)吧
:
: l
| | | g**********y
发帖数: 14569 | 41 别，这不是我解的，我只是记下了当时大家讨论的最佳解。
【在 H****s 的大作中提到】
: 火鸡，还是你牛！PF
| m********l
发帖数: 4394 | 42 我觉的这个主要是要知道什么时候该停
- keep track of remaining length
- keep track of average or sum of remaining elements.
if the difference between current number and subsequent numbers exceed a
threshold (stored), then stop
go to the next number.
【在 d*******l 的大作中提到】
: 这题dp怎么弄？好像不存在递推关系
| d*******l
发帖数: 338 | 43 这个就不是dp了吧。我觉得想做到严格O(n^2)以下还是挺困难的
【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
| b*****c
发帖数: 1103 | 44 我觉得反而怎么检测重复比较难
【在 m********l 的大作中提到】
: 我觉的这个主要是要知道什么时候该停
: - keep track of remaining length
: - keep track of average or sum of remaining elements.
: if the difference between current number and subsequent numbers exceed a
: threshold (stored), then stop
: go to the next number.
| g***y
发帖数: 764 | 45 ido not understand this problem statement
can you please elaborate?
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| r*******g
发帖数: 1335 | 46 假设出现重复的数字，你是怎么处理的。
比如，1,2,2
到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
，不是么？
你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
选出一段不重复的可以组成sequence。
【在 g**********y 的大作中提到】
: 这个题在本版问过，这是当时给的解，去考古一下吧
: public class LongestRange {
: public int[] longest(int[] a) {
: int start = 0;
: int maxLen = 0;
:
: HashMap map = new HashMap();
: for (int i=0; i: int left = map.containsKey(a[i]-1)? map.get(a[i]-1) : 0;
: int right = map.containsKey(a[i]+1)? map.get(a[i]+1) : 0;
| B*******1
发帖数: 2454 | | b*****c
发帖数: 1103 | 48 你就不看看我的回复么，呜呜
火鸡的算法是输出3，4，5，6，7的，不是5,7,4,3,6
【在 r*******g 的大作中提到】
: 假设出现重复的数字，你是怎么处理的。
: 比如，1,2,2
: 到第一个2的时候len是依然是2，但是对应的可以转换为sequence的段应该为1了，这是
: 因为后面的所有的sequence，都不会用第一个2，要从第二个2重新开始计算可能的长度
: ，不是么？
: 你这个好像是算整个一段数可以组成的sequence长度，允许数字重复，但是题目要求是
: 选出一段不重复的可以组成sequence。
| r*******g
发帖数: 1335 | 49 还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
1的序列。
【在 B*******1 的大作中提到】
: 火鸡的代码似乎漏了检测重复，原帖子在这里
: http://www.mitbbs.com/article_t/JobHunting/31911013.html
: 作者的代码是有检测重复的。
| B*******1
发帖数: 2454 | 50 恩，的确有点不一样，但是似乎把连接里面的方法改进一下就可以得到这题的答案了。
【在 r*******g 的大作中提到】
: 还是不一样把，这里是要找连续的一段sequence，这段sequence可以组成一个单调递增
: 1的序列。
| | | s******e
发帖数: 108 | 51 This is harder question.
For example.
int []a =new int[] {4,5,1,5,7,4,3,6,3,1,9,8};
should return {5,7,4,3,6}
rather than {3,4,5,6,7,8,9} or {5,7,4,3,6,9,8}
because it needs to consider that
the index of the elements should also
need to satisfy the condition
of longest consecutive increase sequence.
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| s******e
发帖数: 108 | 52 A partial solution, not finished yet for the existing element.
use two hashtable,
one hashtable used for element value
another hashtable used for element index.
O(n) complexity.
static public int[] longest2(int[] a) {
int start = 0;
int maxLen = 0;
int indexStart =0;
int indexMaxLen =0;
HashMap map = new HashMap();
HashMap indexmap = new HashMap();
for (int i=0; i
Node valNode = map.get(a[i]);
if(valNode==null){
Node newNode = new Node(1,i);
map.put(a[i], newNode);
indexmap.put(i, 1);
Node lowerValNode = map.get(a[i]-1);
if(lowerValNode!=null){
int newVal = lowerValNode.lenVal+1;
Node aiNode = map.get(a[i]);
aiNode.lenVal = newVal;
// map.put(a[i], newVal); //high part
Node startRangeNode = map.get(a[i]-newVal+1);
startRangeNode.lenVal = newVal;
// map.put(a[i]-newVal+1, newVal); //low part
if(newVal >maxLen){
maxLen = newVal;
start = a[i]-newVal+1;
}
//loop1, [a[i]-newVal+1, a[i]]
//check i-1
//check a[i-1] whether in loop1
if( (a[i-1]<=a[i]) && (a[i-1]>=a[i]-newVal+1) ){
//merge i with i-1 in the indexmap
Integer lowerIndexLenVal= indexmap.get(i-1);
int newIndexLenVal = lowerIndexLenVal+1;
indexmap.put(i, newIndexLenVal);
indexmap.put(i-newIndexLenVal+1, newIndexLenVal);
if(indexMaxLen < newIndexLenVal){
indexStart = i-newIndexLenVal+1;
indexMaxLen = newIndexLenVal;
}
}
}
Node highValNode = map.get(a[i]+1);
if(highValNode!=null){
int highVal = highValNode.lenVal;
Node aiNode = map.get(a[i]);
int newVal = aiNode.lenVal + highVal;
Node endRangeNode = map.get(a[i]+highVal);
endRangeNode.lenVal = newVal;
// map.put(a[i]+highValNode.lenVal, newVal);//high part
Node startRangeNode = map.get(a[i]+highVal-newVal+1);
startRangeNode.lenVal = newVal;
// map.put(a[i]+highVal-newVal+1, newVal); //low part
if(newVal >maxLen){
maxLen = newVal;
start = a[i]+highVal-newVal+1;
}
//loop1, [a[i]+highVal-newVal+1,a[i]+highVal]
//check
int p1 = highValNode.index;
Integer p1LenVal = indexmap.get(p1);
//range, [p1,p1+p1LenVal-1]
//check whether in loop1
if(a[p1+p1LenVal]>= a[i]+highVal-newVal+1 && a[p1+
p1LenVal]<= a[i]+highVal){
//merge loop2
Integer len1=indexmap.get(p1+p1LenVal);
int newLen1 = len1+p1LenVal;
indexmap.put(p1, newLen1);
indexmap.put(p1+newLen1-1, newLen1);
if(indexMaxLen < newLen1){
indexStart = p1;
indexMaxLen = newLen1;
}
}
if(a[p1-1]>= a[i]+highVal-newVal+1 && a[p1-1]<= a[i]+
highVal){
Integer len2=indexmap.get(p1-1);
Integer newp1LenVal = indexmap.get(p1);
int newLen2=len2+newp1LenVal;
indexmap.put(p1-len2, newLen2);
indexmap.put(p1-len2+newLen2-1, newLen2);
if(indexMaxLen < newLen2){
indexStart = p1-len2;
indexMaxLen = newLen2;
}
}
}
} else {
valNode.index=i;
indexmap.put(i, 1);
//more to be done
}
// Integer indexVal = indexmap.get(i);
// if(indexVal==null){
//
// }
}
int[] b = new int[maxLen];
for (int i=0; i
b[i] = start + i;
System.out.print(b[i]+" ");
}
System.out.println();
for(Integer key : map.keySet()) {
Integer val = map.get(key).lenVal;
System.out.println("key: "+key+ " val: "+ val);
}
int[] b2 = new int[indexMaxLen];
for (int i=0; i
b2[i] = indexStart + i;
System.out.print(a[b2[i]]+" ");
}
System.out.println();
return b;
}
.:
【在 i**d 的大作中提到】
: you have an array of integers, find the longest
: subarray which consists of numbers that can be arranged in a sequence, e.g.:
: a = {4,5,1,5,7,4,3,6,3,1,9}
: max subarray = {5,7,4,3,6}
: 只能想到brute force的方法。有什么好的办法来做么？
: 谢谢了。
| n*******w
发帖数: 687 | 53 同感。
跑了下3个数字就崩溃了。
【在 B*******1 的大作中提到】
: 火鸡的代码似乎漏了检测重复，原帖子在这里
: http://www.mitbbs.com/article_t/JobHunting/31911013.html
: 作者的代码是有检测重复的。
| h*****n
发帖数: 93 | 54 my two cents:
1.先做个bit map.O(N) time. bitmap中放数在array中的位置.
bitmap(i) = position of i in Array.
2. bitmap中连续的数,按array中的位置,那bitmap的value排序. 最坏O(NlogN)
2b. 对排序的数找最长连续数列 (需要考虑重复数字). O(N)
好像重复的数字也可以. | r*******g
发帖数: 1335 | |
|
