D*******e
发帖数: 151 | 1 Given an array of integers A, give an algorithm to find the longest
Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such
that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest possible. The sequence S1, S2, …, Sk is called an arithmetic
progression if Sj+1 – Sj is a constant. | i*******h
发帖数: 216 | 2 I feel that a sort is necessary, so at least O(NlgN). After that, a brutal
force can solve it in O((N**2)*lgN). Can remove the lgN if hash table is
used.
Simply put, for each element Ai, for each element Aj after Ai, get their
delta, and then check if Aj+delta is in.
Maybe DP is better? | d*******l
发帖数: 338 | 3 你这好像是n^3的，对于每个Ai和Aj，你都要检查Aj+d,Aj+2d,Aj+3d。。这样才能找出
哪个最长
【在 i*******h 的大作中提到】
: I feel that a sort is necessary, so at least O(NlgN). After that, a brutal
: force can solve it in O((N**2)*lgN). Can remove the lgN if hash table is
: used.
: Simply put, for each element Ai, for each element Aj after Ai, get their
: delta, and then check if Aj+delta is in.
: Maybe DP is better?
| s*****n
发帖数: 994 | 4 int findLongestRegression (int array[], int size){
if (size<=0) return 0;
sort (arrary, array+size);
int maxgap = array[size-1]-array[0];
int gap;
int start,next,current;
int k, maxk=0;
for (gap=1;gap<=maxgap;gap++){
for (start=0; start
if (array[start]>=array[0]+gap) break;
k=0;
current = start;
for (next=start+1; next
if (array[next]-array[current]==gap){
k++; current = next;
}
}
if (k>maxk) maxk=k;
}
}
return maxk;
}
This algorithm above is not very efficient. The one below is more efficient:
1. sorting
2. for each gap between 1 to maxgap
3. new an array len with size gap-1, len[i] is how long the list of element
% gap == i;
4. divide array into segments, segment_i between [array[0]+*gap,array[0]+(i+
1)*gap]
5. go through each segment, add len[i] if these still new element in the
list_i
This algorithm for each gap is n, so n^2
【在 D*******e 的大作中提到】
: Given an array of integers A, give an algorithm to find the longest
: Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such
: that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
: largest possible. The sequence S1, S2, …, Sk is called an arithmetic
: progression if Sj+1 – Sj is a constant.
| d******i
发帖数: 54 | 5 The problem requires i1 < i2 < … < ik, so I don't think sorting will work,
since sorting will break the original order of the indices... | r*******g
发帖数: 1335 | 6 如果空间不受限，我会在每个节点维护一个hash表，这个hash表是到达这个节点以前的
progression的长度，key是这个节点前面所有的节点，value是progression长度
当然先要排序。
基于这个表，从做到右DP就行了。时间N^2.
【在 D*******e 的大作中提到】
: Given an array of integers A, give an algorithm to find the longest
: Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such
: that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
: largest possible. The sequence S1, S2, …, Sk is called an arithmetic
: progression if Sj+1 – Sj is a constant.
| r*******g
发帖数: 1335 | 7 oh
你说的对，不过dp还是可以做，就是空间要求高。
,
【在 d******i 的大作中提到】
: The problem requires i1 < i2 < … < ik, so I don't think sorting will work,
: since sorting will break the original order of the indices...
| d*******l
发帖数: 338 | 8 我觉得这个想法是正确的，不过我觉得key是所有可能的d比较合适。另外这个方法不需
要排序吧？
【在 r*******g 的大作中提到】
: 如果空间不受限，我会在每个节点维护一个hash表，这个hash表是到达这个节点以前的
: progression的长度，key是这个节点前面所有的节点，value是progression长度
: 当然先要排序。
: 基于这个表，从做到右DP就行了。时间N^2.
| d******i
发帖数: 54 | 9 Sounds great to me. No sorting is need since the problem requires i1 < i2 <
… < ik
【在 d*******l 的大作中提到】
: 我觉得这个想法是正确的，不过我觉得key是所有可能的d比较合适。另外这个方法不需
: 要排序吧？
| D*******e
发帖数: 151 | 10 I only know brute force, O(N^3)
If we can sort it, it can be solved in O(N^2), which is optimal | d******i
发帖数: 54 | |
|
