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 | |
|