数组的数据结构问题 - 如何在给定条件下找到最佳数组

Question

我是新手，正在学习数据结构和算法，我需要帮助来解决这个问题

具有N个元素的数组的最佳值定义为Array所有元素的最佳值之和。元素A[i]中的best定义如下

a: The best of element A[i] is 1 if, A[i-1]<A[i]<A[i+1]
b: The best of element A[i] is 2 if, A[i]> A[j] for j ranging from 0 to n-1
                                 and A[i]<A[h] for h ranging from i+1 to N-1

编写程序找出数组的最佳

注意- A[0]和A[N-1]被排除在外找到最好的数组，所有元素都是唯一的

输入 - 2,1,3,9,20,7,8

输出 - 3

最好的元素3是2，9是1。其余元素是0。因此2+1 =3

这是我到目前为止尝试过的-

public static void main (String [] args) {
        
    int [] A = {2,1,3,9,20,7,8};
        
    int result = 0;
                
    for(int i=1; i<A.length-2; i++) {
        if(A[i-1] < A[i] && A[i]< A[i+1] ) {
            result += 1;
        }else if(A[i]>A[j] && A[i]<A[h]){
            result +=2;
        }else {
            result+=0;
        }
    }   
}

Answer 1

注意短语：

A[i]> A[j] for j ranging from 0 to n-1

简单的意思是：如果当前元素是不是数组的Minimum。因此，如果你在一开始就找到最小值，这个条件可以变成一个更简单和轻量级的条件：

 Let m be the minimum of the array, then if A[i] > m

因此您不需要每次迭代都进行线性搜索 --> 时间复杂度更低。

现在您的问题复杂度为 O(N^2)，..可以进一步降低。

关于

and A[i]<A[h] for h ranging from i+1 to N-1

获取从2到N-1的最大元素。然后在每次迭代中，检查当前元素是否小于最大值。如果是，则在打分时考虑，否则，说明当前元素是最大值，此时重新计算最大元素从i+1到N-1。

最坏的情况是找到最大值总是在索引 i 处，其中数组已经按降序排序。

而最好的情况是最大值始终是最后一个元素，因此整体复杂性降低到 O(N)。

关于

A[i-1]<A[i]<A[i+1]

这很简单，您只需在每次迭代时比较驻留在这三个索引处的元素。

实施

首先，以下是重要说明：

您在示例中得到的结果不正确，因为元素 3 和 9 两者都满足两个条件，所以每个应该得分1或2，但不能是一个得分为1而另一个得分为2。因此总得分应该是1+1 = 2或2 + 2 = 4.

我在 Java 中实现了这个算法（虽然我更喜欢 Python），正如我从你的代码片段中猜到的那样。

import java.util.Arrays;

public class ArrayBest {

private static int[] findMinMax(Integer [] B) {
    // find minimum and the maximum: Time Complexity O(n log(n))
    Integer[] b = Arrays.copyOf(B, B.length);
    Arrays.sort(b);
    return new int []{b[0], b[B.length-1]};
}

public static int find(Integer [] A) {
    // Exclude the first and last elements
    int N = A.length;
    Integer [] B = Arrays.copyOfRange(A, 1, N-1);
    N -= 2;

    // find minimum and the maximum: Time Complexity O(n log(n))
    // min at index 0, and max at index 1
    int [] minmax = findMinMax(B);

    int result = 0;

    // start the search
    for (int i=0; i<N-1; i++) {
        // start with first condition : the easier
        if (i!=0 && B[i-1]<B[i] && B[i]<B[i+1]) {
            result += 1;
        }else if (B[i] != minmax[0]) {  // Equivalent to A[i]> A[j] : j in [0, N-1] 
            if (B[i] < minmax[1]) {  // if it is less than the maximum
                result += 2;
            }else { // it is the maximum --> re-calculate the max over the range (i+1, N)
                int [] minmax_ = findMinMax(Arrays.copyOfRange(B, i+1, N));
                minmax[1] = minmax_[1];
            }
        } 
    }
    return result;
}
public static void main(String[] args) {
    Integer [] A = {2,1,3,9,7,20,8};
    int res = ArrayBest.find(A);
    System.out.println(res);
}

}

忽略第一种排序，最佳情况 是最后一个元素最大（即在索引 N-1 处），因此时间复杂度为 O(N).

最坏的情况是当数组已经按降序排序时，因此正在处理的当前元素始终是最大值，因此在每次迭代中应该再次找到最大值。因此，时间复杂度为 O(N^2).

平均情况 取决于元素在数组中的分布概率。换句话说，元素在当前迭代中被处理的概率是最大的。虽然还需要进一步研究，但我的初步猜测如下：

任何i.i.d元素成为最大值的概率只是1/N，那是在最开始的时候，但是随着我们搜索（i+1，N-1), N 将减少，因此概率将变为：1/N, 1/(N-1), 1/(N-2), ..., 1。算上外循环，我们可以将平均复杂度写为 O(N (1/N + 1/(N-1), 1/(N-2), + ... +1)) = O(N (1 + 1/2 + 1/3 + ... + 1/N))，其中其渐近上限（根据调和级数）约为 O(N log(N)).

数组的数据结构问题 - 如何在给定条件下找到最佳数组

Data Structure Question on Arrays - How to find the best of array given conditions

arrays

loops

data-structures

实施