算法找不到。大小为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)); 
}  
}