查找了一些流AP三胞胎的數量

Question

問題：

考慮N個整數A1，A2，...。 AN，德克斯特想知道他有多少種方式可以選擇三個數字，這樣他們就算是連續三個算術級數。

CodeChef link。

這裏是我的解決方案（讓「頻率」是計數器）

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]; 
    } 
} 

以下是我在尋找：

1. 當我提出這個問題，我得到的「時間限制突破」。因此，我想使用NetBeans Profiler來估計此解決方案需要的時間，以便我可以改進它。 僅供參考 - 時間限制成功提交爲3秒

2. 誰能給我一些指點，以提高我的解決方案[我不想改變我的解決方案]由：

   • 優化存儲
   • 哪我的解決方案的部分被耗時的，並且有一個明顯的解決方法

實施例：

輸入：

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) 

Answer 1

我沒有檢查你的代碼的細節，但這裏是我會怎麼做：

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 

Answer 2

您應該實現數據存儲的lazy instantiation。

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)

Answer 3

大想法，如果你有前兩項，那麼第三項是固定的。

利用內存你可以做得更好。

讓我們有一個數組的數組。我不知道你如何在Java中做這個，這裏是C++版本。

vector<vector<int> > where

其中，[i]於輸入 =位置處值= I

所以{1,4,2,3,3}會是什麼樣

where[0]={} 
where[1]={0} 
where[2]={2} 
where[3]={3,4} 
where[4]={1} 

如果你初始化矢量的上述向量，那麼位置將被排序。

再次，您可以設置AP的前2個元素，而不是在原始輸入流中搜索第三個元素，您可以在其中輕鬆查找它。

我總是用下面的算法結束算法問題：我們可以做得更好嗎？我確信有更好的方法，如果我打了它，我會更新這個答案。