问题：
给定N个整数A1，A2…。安，德克斯特想知道有多少种方法可以选择三个数字，使它们成为算术级数的三个连续项。
CodeChef链接。
这是我的解决方案（让"freq"是计数器）
1. Create a data store (array of sorted sets) to hold a sorted set of positions of number i in stream at index i in array.
2. for k: 0 to array.length
a. get Sorted Set S[k]
b. if SZ >=3, where SZ = S[k].size, compute SZ choose 3 and add it to freq
c. for r: 2*k-1 to k
for x in S[k]
find entries in S[r], say A, more than x and entries in S[r-i], say B, less than x.. freq += A*B
find entries in S[r], say A, less than x and entries in S[r-i], say B, more than x.. freq += A*B
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
/**
*
* @author abhishek87
*/
class APTripletInStream {
public static void main(String[] args) {
int idx=0, numInStream;
Scanner scanIn = new Scanner(System.in), readLine;
String line = scanIn.nextLine();
readLine = new Scanner(line);
DataStore dStore = new DataStore(30000 + 1);
while(scanIn.hasNextLine()) {
line = scanIn.nextLine();
readLine = new Scanner(line);
while(readLine.hasNextInt()){
numInStream = readLine.nextInt();
dStore.add(++idx, numInStream);
}
break;
}
Long res = 0L;
try {
res = APProblemSolver.solveProblem(dStore);
} catch(Exception ex) {
res = 0L;
}
System.out.println(res);
}
}
class APProblemSolver {
public static Long solveProblem(DataStore dStore) {
Long freq = 0L;
int dSize = dStore.size();
for(int idx=1; idx<=dSize-1; idx++) {
Set currSet = dStore.getSetAtIndex(idx);
if(null != currSet && !currSet.isEmpty()) {
int size = currSet.size();
if(size >= 3) {
freq += (size*(long)(size-1)*(long)(size - 2)/6L);
}
for(int right = 2*idx-1; right > idx; right--){
if(right >= dSize)
continue;
Set rightSet = dStore.getSetAtIndex(right);
Set leftSet = dStore.getSetAtIndex(2*idx - right);
if(null != rightSet && null != leftSet) {
for(Object obj : currSet) {
Set leftSetHeadSet = ((TreeSet)leftSet).headSet(obj);
Set rightSetTailSet = ((TreeSet)rightSet).tailSet(obj);
freq += leftSetHeadSet.size() * rightSetTailSet.size();
Set leftSetTailSet = ((TreeSet)leftSet).tailSet(obj);
Set rightSetHeadSet = ((TreeSet)rightSet).headSet(obj);
freq += leftSetTailSet.size() * rightSetHeadSet.size();
}
}
}
}
}
return freq;
}
}
class DataStore {
private TreeSet[] list = null;
private int size;
public DataStore(int size) {
this.size = size;
list = new TreeSet[size];
}
public void add(Integer idx, Integer val) {
Set<Integer> i = list[val];
if(null == i) {
i = new TreeSet<Integer>();
i.add(idx);
list[val] = (TreeSet<Integer>)i;
} else{
((TreeSet<Integer>)list[val]).add(idx);
}
}
public int size() {
return size;
}
public Set getSetAtIndex(int idx) {
return list[idx];
}
}
以下是我想要的：
当我提交问题时，我会得到"超过时间限制"。因此，我想使用NetBeans Profiler来估计这个解决方案所需的时间，以便改进它。仅供参考-成功提交的时间限制为3秒
有人能给我一些改进我的解决方案的建议吗
- 优化存储
- 我的解决方案的哪些部分很耗时，并且有明显的解决方法
示例：
输入：
Number Of entries - 10.
Number Stream - 3 5 3 6 3 4 10 4 5 2.
输出：
9.
说明：
The followings are all 9 ways to choose a triplet:
(Ai, Aj, Ak) = (3, 3, 3)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (6, 4, 2)
(Ai, Aj, Ak) = (6, 4, 2)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)
我还没有详细检查您的代码，但我会这样做：
Sort your list -- 1
Iterate through your sorted list (i from 0 to n) -- 2
Iterate though the remaining part of the list (j from i+1 to n) -- 2.a
Lookup if (2*j-i) which would be the third element of the arithmetic progression -- 2.a.1
步骤1是O（n*log（n）），但由于二进制搜索，它允许步骤2.a.1为O（log（n-j））。
以下是我的python实现：
from bisect import bisect_left
def index_in_sorted(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
return None
numbers=[4,5,6,17,9,1,442,44,32,3,21,19]
print numbers
numbers.sort()
n = len(numbers)
for i in range(0,n):
n_i = numbers[i]
for j in range(i+1,n):
n_j = numbers[j]
n_k = 2*n_j - n_i
if index_in_sorted(numbers,n_k): # I could only process the end of numbers but it's not worth the pain
print "Found", n_i,n_j,n_k
您应该实现数据存储的延迟实例化。
public DataStore(int size) {
for(int i=0; i<size;i++)
list.add(i, new TreeSet<Integer>());
}
您可以在实例化过程中创建30001个树集。最好将所需内容映射到int -> Set。然后在您的代码dStore.getSetAtIndex(right)中，如果没有为这个int设置，则实例化它
显而易见的部分是：
for(Object objMore : leftSetTailSet) {
for(Object objLess : rightSetHeadSet) {
freq++;
}
}
可以更改为freq += leftSetTailSet*rightSetHeadSet;
此外，我没有看到dsStore的大小发生变化，所以：
而不是：在for循环中的idx<=dStore.size()-1;，您可以声明变量dsSize = dStore.size()，并具有idx < dsSize和if(right >= dsSize)
大的想法是，如果你有前两个术语，那么第三个术语是固定的。
利用内存你可以做得更好。
让我们有一个数组。我不知道你是如何在Java中做到这一点的，这是C++版本。
vector<vector<int> > where
其中[i]=输入中的位置值=i
所以{1,4,2,3}看起来像
where[0]={}
where[1]={0}
where[2]={2}
where[3]={3,4}
where[4]={1}
如果你初始化上面向量的向量where，那么位置就会被排序。
同样，您可以设置AP的前两个元素，现在不用在原始输入流中搜索第三个元素，而是可以在中轻松查找，其中。
我总是在结束算法问题时说：我们能做得更好吗？我相信有更好的方法，如果我找到了，我会更新这个答案。