算法涉及分区和选择

据我所知，这个问题可以通过利用选择和分区，这两者都可以在线性时间内完成最有效地得到解决。我的想法是选择数组O（n）中的第n个最小元素，在这个例子中给出的将是34，所以在这种情况下为j = 3。然后from i = 1 to j - 1，如果序列递减，则设置B[i] = j，序列增加的那一刻，设置B[i] = i + 1并停止。递归调用数组A[j ... n]上的过程。我不认为这是有效的，也不确定它是否正确，或者算法的最终复杂程度如何。

摘要

（1）选择第n个最小（索引j）利用确定性选择算法O（N）

（2）

function: 
    for i = 1 to n do 
     for j = i + 1 to n do 
     if A[j] > A[i] then B[i] = j , B[j] = n + 1 
     for k = i + 1 to j - 1 do 
      if A[k] < A[k + 1] 
       B[k] = j 
      else 
       B[k] = k + 1 
       recursive function(A[j + 1, ... n]) // recursively perform procedure on portion of array starting from j + 1 (after max) to n.

来源

2015-10-17 Mutating Algorithm

也许你可以使用合并排序（O（nlogn）），你可以将两个数组分成n个子列表，每个列表包含1个元素。然后重复合并子列表以获得新的已排序的子列表，直到只剩下1个子列表。 –

@VictorLuna我认为这是一个正确的解决方案，但不是最有效的。我相信这个问题可以在O（n） –

中完成。实际上合并排序它不是O（nlogn），它是O（n + m）。因为列表就像队列一样，所以它们指向要在每个数组中使用的下一个元素。在插入它们之前比较这些值时，确切地说有n + m个比较，使其在运行时为O（n）。 –

有一个标准的基于堆栈的解决方案来这个问题是O（n）。在http://www.geeksforgeeks.org/next-greater-element/有一个很好的解释。

下面是一个例子Python实现该算法的：

def next_greater_element(A): 
    """Return an array of 1-based indices to the next strictly greater element, n+1 if none exists""" 
    i=0 
    n = len(A) 
    NGE=[n+1]*len(A) 
    stack=[] 
    while i<len(A)-1: 
     stack.append(i) 
     while stack and A[stack[-1]]<A[i+1]: 
      x=stack.pop() 
      NGE[x]=i+2 
     i+=1 
    return NGE 

A = [8,3,34,13,1,2,21,5] 
B = next_greater_element(A) 
print B

这将打印

[3, 3, 9, 7, 6, 7, 9, 9]

主要的一点是每个元件被压入堆栈一次，并且可以被弹出的堆栈一次，所以inner while循环最多可以执行n次。

来源

2015-10-17 19:26:50

只是为了好玩，这里是在C基于堆栈的解决方案，这原来是特别简洁：

#include <stdio.h> 

void find_next_largest(int *a, int *b, int n) { 
    int s[n], p = -1; 
    for (int i = 0; i < n; i++) { 
    while (p >= 0 && a[i] > a[s[p]]) b[s[p--]] = i; 
    s[++p] = i; 
    } 
    while (p >= 0) b[s[p--]] = n; 
} 

int main(void) { 
    int a[] = { 8, 3, 34, 13, 1, 2, 21, 5, }, b[100]; 
    int n = sizeof a/sizeof a[0]; 
    find_next_largest(a, b, n); 
    for (int i = 0; i < n; i++) printf("%d ", b[i] + 1); 
    printf("\n"); 
    return 0; 
}

算法的核心思想是，a每一个新的“下一个”元素要么增加到一个不增加的尾部（它小于或等于最后一个元素），要么增加。在后一种情况下，我们希望通过非增长尾部后退，记录新元素是其下一个最大元素，在找到相等或更大元素时停止，然后推入新元素。堆栈是用于向后搜索先前遇到的数据的完美数据结构。数组s是堆栈。它将索引存储到等待下一个最大的元素的a中。

请注意，如果新的a元素不大于前一个元素，当新元素isn'时，停止弹出时，找到等于或更大的元素，然后推新元素“比前一次大t。它弹出零个元素并推送新的元素。

另请注意，由s引用的a元素总是按照从头开始的升序排列。

来源

2015-10-18 18:44:37 Gene

算法涉及分区和选择

回答

相关问题