2

建议？

给定一个未排序的数组和元素的数量，对于每个元素，如果没有数字 -1，我必须打印其自身与数组中小于他的最远元素之间的元素数量

例子：

输入：10 6 10 3 9 15 输出：3 1 1 -1 -1 -1

我已经做到了，但是我的教授告诉我它可以做得更高效，当然我实际上在做 o(n^2)。分而治之？，二分查找？

我的解决方案：

public void MedidaMolestia(int A[], int  N)
    {
    int i=0,  temp=0, k=N-1, j=0;

    for(i=0; i<N; i++) 
    {
        temp = A[i];

        for(j=N-1;j>i ; j--)
        {
            if(A[j]<temp)
            break;
        }

        if(i==j)
            System.out.print(-1 + " ");

        else 
            System.out.print((j-i)-1 + " ");
    }
}
4

1 回答 1

0

即兴发挥，我可以建议使用一点动态编程进行一些渐近改进：-

  1. 使用快速排序来获取排序版本数组中每个元素的索引。花费 O(n log n)。对于您的示例，它应该是：-

    sindex = [3 1 3 0 5 2] ( since sorted array is 3 6 9 10 10 15)

  2. 您需要填充数组 B，以便 B[i] 存储小于 i 的索引最右边的第一个出现。执行以下操作：-

    Initialize B to [N, N,...]
filledpos = N;
for j = N-1 to 0 inclusive
    if(sindex[j] < filledpos) do 
    for i = sindex[j] to filledpos - 1 inclusive 
    // like if you find the 3rd smallest element fill B[4],.. B[filledpos]
       B[i] = j
    filledpos = sindex[j]

    对于您的示例 B = [2 2 3 3 5 5]。采用 O(n) 最坏情况

  3. 现在你知道了最右边 elem < i 的位置。做foll（需要O（n））

    for i = 0 to N-1
   print i - B[sindex[i]]
于 2012-12-03T21:43:49.103 回答