数组中最远的小元素 [英] Farthest Smaller Element in an Array

问题描述

在一个未排序的正整数数组中，如何最有效地找出每个元素右边最远的小元素?

In an unsorted positive integer array, how to find out the farthest smaller element on the right side of each element in most efficient way?

例如:
输入:6 3 1 8 2 9 7
输出:2 2 -1 7 -1 7 -1

Ex:
Input: 6 3 1 8 2 9 7
Output: 2 2 -1 7 -1 7 -1

说明:

对于 6，它右侧的较小元素是 [3, 1, 2].因为最后一个最小的元素是 2，所以它离 6 最远.像对别人一样聪明.如果不存在这样的数字，则答案为-1"

For 6, the smaller elements on it's right side are [3, 1, 2]. Since the last smallest element is 2, it's the most farthest from 6. Like wise for others. If no such number exists answer is "-1"

推荐答案

一个想法是:

• 让我们调用原始数组 A
• 保留一个大小为 n 的数组 min[]，其中 min[i] 表示子数组 A[i..n-1] 的最小值.显然，min[i] <= min[i+1].
• 现在在 A 上从右向左移动.在每个索引 i 上，对 min[i+1..n-1] 进行二分搜索以找到最远的较小值.

Java 代码:

    int[] A = { 6, 2, 3, 10, 1, 8 };
    int n = A.length;
    // calculate min
    int[] min = new int[n];
    min[n - 1] = A[n - 1];
    for (int i = n - 2; i >= 0; i--)
        min[i] = Math.min(A[i], min[i + 1]);
    // calculate results
    int[] results = new int[n];
    results[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--) {
        int left = i; // after the binary search, A[left] would be the answer
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (min[mid] < A[i])
                left = mid;
            else
                right = mid - 1;
            if (min[left] < A[i])
                results[i] = min[left];
            else
                results[i] = -1;
        }
    }

空间复杂度 O(n)

所有情况的时间复杂度为 O(nlogn).

Time complexity O(nlogn) for all cases.

与@vivek_23 的解决方案相比，上述算法在以下最坏情况下会更好:

Compared to the solution from @vivek_23, the above algorithm would be better in the following worst case:

想象一下有 n 个元素的 A 的情况如下

Imagine the case of A of n elements as follows

A = [ n/2 n/2 .. n/2 1 2 .. n/2]

A = [ n/2 n/2 .. n/2 1 2 .. n/2]

如果我们使用@vivek_23 建议的堆栈解决方案，

If we use the stack solution suggested by @vivek_23,

• 在寻找前 n/2 个元素(均值为 n/2)中最远的小元素的步骤中，st1 现在应该是 [1 2 .. n/2]
• 对于每个值为 n/2 的元素，除了 n/2 之外的所有 st1 元素都将被转移到 st2，以便找到最远的小元素 n/2 - 1.之后 st2 中的所有元素将被转移回 st1.这导致 O(n) 的最坏情况性能.由于有 n/2 个元素，因此总的最坏时间性能为 O(n^2).

这篇关于数组中最远的小元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！