算法找不到。大小爲n的子集，其中每個元素都小於其前一個元素，索引是第一個元素是最少的

Question

我有一個數組，可以說{7,6,4,2}。

我需要一個高效算法找到次數n較小的數字發生在給定的元素之後，其中每個元素都小於前一個元素。

例如：對於n=3,a[i]>a[j]>a[k]和i < j < k。這裏的輸出應該是{7,6,4},{7,6,2}和{6,4,2}。

我有一個簡單的算法與3 for循環，但顯然與O(n^3)複雜性的解決方案是不可行的。

以下是我爲n=3創建的示例代碼。

// Array is initialized and given values. Size of Array is n1 
for(int i=0;i<n1-2;i++) 
{ 
    for(int j=i+1;j<n1-1;j++) 
    { 
     if(a[j]<a[i]) 
     { 
      for(int k=j+1;k<n1;k++) 
      { 
       if(a[k]<a[j]) 
       { 
        cnt++; 
       } 
      } 
     } 
    } 
}  

可否請你聯繫我的算法，我可以使用或我提供以下算法。 JAVA首選。

Answer 1

如果你拿{7,6,11,2}，你可以建立一個圖，其中節點是7,6,11和2，並且只有在另一個節點索引較大且值較小。構建這樣的圖應該是O（len（a）^ 2）。

構建圖形後，您可以編寫一個遞歸函數來計算可以達到3個連續節點的次數。複雜性是O（n * len（a））。

我的解決方案（僅適用於第一要素考慮，但它是微不足道的適應）：

#include <stdio.h> 
#include <stdlib.h> 

struct succ { 
    struct node* node; 
    struct succ* next; 
}; 

struct node { 
    struct succ* successors; 
    int value; 
    int index; 
}; 

struct node* build_graph(int a[], int n1) { 
    struct node* graph = malloc(n1 * sizeof(struct node)); 
    int i, j; 
    for (i = 0; i < n1; i++) { 
     graph[i].value = a[i]; 
     graph[i].index = i; 
    } 

    for (i = 0; i < n1; i++) { 
     for (j = i; j < n1; j++) { 
      if (a[i] > a[j]) { 
       struct succ *el = malloc(sizeof(struct succ)); 
       el->node = &graph[j]; 
       el->next = graph[i].successors; 
       graph[i].successors = el; 
      } 
     } 
    } 

    return graph; 
} 

int browse(struct node* graph, int i, int n) { 
    if (n == 0) return 1; 

    struct succ *aux = graph[i].successors; 
    int cnt = 0; 
    while (aux) { 
     cnt += browse(graph, aux->node->index, n - 1); 
     aux = aux->next; 
    } 

    return cnt; 
} 

int main() { 
    //int a[] = {7, 6, 11, 2}; 
    int a[] = {7, 6, 4, 2}; 

    struct node* graph = build_graph(a, 4); 

    printf("%d\n", browse(graph, 0, 2)); 

    return 0; 
} 

Answer 2

import java.util.*; 
import java.io.*;  

class CDVA1510 
{ 
public static void main(String[] args) throws Exception 
{ 
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in)) 
    int n=Integer.parseInt(br.readLine()); 
    String[]a1=br.readLine().split(" "); 
    long[] a=new long[a1.length()]; 
    for(int j=0;j<a.length();j++) 
    { 
    a[j]=Integer.parseInt(a1[j]); //Storing the values 
    } 
    ArrayList<Long>al=new ArrayList<Long>();//Sorted List for storing the values 
    ArrayList<Integer>nos=new ArrayList<Integer>();//List for adding number of numbers before the given number with which combinations are possible 
    int []no=new int[n]; 
    for(int j=n-1;j>=0;j--) 
    { 
     al.add(a[j]); 
     Collections.sort(al); 
     if(al.indexOf(a[j])>=2)//Getting postion of element and since implementation is specific, checking if it it greater than or equal to 2 so that x(this number) choose 2 is possible 
     { 
      nos.add(al.indexOf(a[j])); 
      //System.out.println(a[j]); 
     } 
    } 
    int cnt=0; 
    for(int j=0;j<nos.size();j++) 
    { 
     cnt += COM(nos.get(j)); 
    } 
    System.out.println(cnt); 
} 
private static long COM(long a)//Method for getting the combinations. Again specific for n=3 
{ 
    int x=1,y=1; 
    for(int i=1;i<=a;i++) 
    { 
     if(i<=a-2) 
     { 
      x = x * i; 
      y = y * i; 
     } 
     else 
     { 
      x=x*i; 
     } 
    } 
    return((x)/(y*2)); 
}  
}