整數數組中包含3個遞減值的組的數量（低於O（n^3）時間）

Question

遞減三元組定義爲一組3個值{a，b，c}，其大小從左到右遞減這樣a> b> c。

如何找到一個整數數組中三元組的數目，其中三元組{i，j，k}的索引正在增加，這樣我就可以找到這些三元組的數目。

例如，考慮下面的例子：

{4, 5, 2, 1} 
2 decreasing triples: {4, 2, 1} and {5, 2, 1} 

{6, 1, 2, 4, 5, 3} 
2 decreasing triples: {6, 5, 3} and {6, 4, 3} 

{5, 4, 3, 2, 1} 
10 decreasing triples: 
{5, 4, 3}, {5, 4, 2}, {5, 4, 1}, {5, 3, 2}, {5, 3, 1}, 
{5, 2, 1}, {4, 3, 2}, {4, 3, 1}, {4, 2, 1}, {3, 2, 1} 

的爲O（n^3）的解決方案是微不足道當然;這裏是在Java中實現： *注：數組是多頭的，但是這是一個輕微的實現細節

public static long countTriples(long[] measurements) 
{ 
    // O(n^3) 
    long count = 0L; 

    for(int i = 0; i < measurements.length; i++) 
    { 
     for(int j = i + 1; j < measurements.length; j++) 
     { 
      if (measurements[j] < measurements[i]) 
      { 

       for(int k = j + 1; k < measurements.length; k++) 
       { 
        if (measurements[k] < measurements[j]) 
        { 
         count++; 
        } 
       } 
      } 
     } 
     } 
    return count; 
    } 
} 

我開始了O（n）的方法來定位降低三元;它成功地確定了三元組，但是當一個給定的三元組的中間值涉及多於一個時，我無法將其計數。下面是我的，現在右：

public static long countTriples(long[] measurements) 
{ 
     ArrayList<Long> greaterOnLeft = new ArrayList<Long>(); 
     ArrayList<Long> lessOnRight = new ArrayList<Long>(); 

     HashSet<Long> min = new HashSet<Long>(); 
     min.add(measurements[measurements.length - 1]); 
     HashSet<Long> max = new HashSet<Long>(); 
     max.add(measurements[0]); 

     for(int i = 0; i < measurements.length; i++) 
     { 
      min.add(measurements[measurements.length - i - 1]); 
      max.add(measurements[i]); 
      System.out.println("max: " + max + ", min: " + min); 
      for(long n : max) 
       if (measurements[i] < n) greaterOnLeft.add(measurements[i]); 
      for(long n : min) 
       if (measurements[measurements.length - i - 1] > n) lessOnRight.add(measurements[measurements.length - i - 1]); 
     } 

     long count = 0; 
     for(long n : greaterOnLeft) 
     { 
      if(lessOnRight.contains(n)) count++; 
     } 
     return count; 
} 

這種方法的想法來自HashSet的方法，從這個職位定位這樣的tripples的中間指標：

How to find 3 numbers in increasing order and increasing indices in an array in linear time

Answer 1

我相信這可以爲O（n^2）時間，而平凡解決：

public static long countTriples(long[] measurements) 
{ 
    // O(n^2) 
     long count = 0; 
     for(int i = 1; i < measurements.length - 1; i++) 
     { 
      long right = 0, left = 0; 

      for(int j = 0; j < measurements.length; j++) 
      { 
       if(j < i && measurements[j] > measurements[i]) right++; 
       else if (j > i && measurements[j] < measurements[i]) left++; 
      } 
      count += right * left; 
     } 
     return count; 
}