从给定数组中查找最小总和

Question

我有一个数字数组

[3,4,5,1,2,3,1]

找到

3 pairs

子序列说

sub[]

这样

sub[0] < sub[1] > sub[2]

，将这3个元素相加并得到最小总和。

示例：

对于

[3,4,5,1,2,3,1]

，我可以在这里选择

[1,2,1]

1<2>1

，所以总和是

1+2+1 = 4

，这是最小值。

限制：

数组大小可达 1,00,000 每个元素大小为 1 到 1,00,00,00,000

我的方法是使用3个嵌套的for循环并获得最小总和，这不是一个有效的方法。

public long process(List<Integer> list) {
   int n = list.size();
   long output = Long.MAX_VALUE;
   for(int i=0; i<n; i++) {
      for(int j=i+1; j<n; j++) {
       if(list.get(i) < list.get(j)) {
          for(int k=j+1; k<n; k++) {
            if(list.get(j) > list.get(k)) {
               output = Math.min(output, list.get(i)+list.get(j)+list.get(k));
             }
          }
       }
      }
   }
   return output;
}

如何以较低的时间复杂度高效地解决这个程序？

Answer 1

让我提供一个解决方案，其时间复杂度为

O(n)

，空间复杂度为

O(n)

。您必须遍历数组三次，并为最小元素存储两个数组。我受到@Someone 的评论的启发。请记住，该解决方案假设对于任何

sub[i] < sub[j] > sub[k]

都必须成立：

i < j < k

。

解决方案可以轻松修改以涵盖

i <= j <= k

的情况。如果这个方程不强制成立，那么问题就变得更加微不足道。只要找到前三个最小元素，我们就知道

sub[i] < sub[j] > sub[k]

成立。确保第三个（最大的一个）与其他的不同。尽管您没有指定我上面提到的规则，但我相信问题希望您遵守该规则 - 否则那将是非常微不足道的。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Stackoverflow {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(3,4,5,1,2,3,1));
        System.out.println(process(numbers));
    }
    
    public static long process(List<Integer> list) {
        if(list.size() < 3) return -1; // not enough elements
        
        int n = list.size();
        
        int[] minLeft = new int[n];
        int[] minRight = new int[n];
        
        minLeft[0] = list.get(0);
        minRight[minRight.length - 1] = list.get(list.size() - 1);
        
        // store the minimum elements from left up to current index
        for(int i=1; i<n; i++) {
            minLeft[i] = Math.min(list.get(i), minLeft[i - 1]);
        }
        
        
        // store the maximum elements from right up to current index
        for(int i=n - 2; i>=0; i--) {
            minRight[i] = Math.min(list.get(i), minRight[i+1]);
        }
        
        
        long sum = Integer.MAX_VALUE;
        
        for(int i=1; i<n-1; i++) {
            sum = Math.min(sum, minLeft[i - 1] + list.get(i) + minRight[i + 1]);
        }
        
        return sum;
    }
}

输出：

4

Answer 2

添加了较小约束的相同代码以考虑极端情况：

公共类minimumSubsequence { 公共静态无效主（字符串[] args）{ ArrayList 数字 = new ArrayList<>(Arrays.asList(3, 4, 5, 1, 2, 3, 1)); System.out.println(minimumSubsequence.getMinimumSum(numbers)); }

public static long getMinimumSum(List<Integer> arr) {
    if (arr.size() < 3)
        return -1;

    int n = arr.size();
    int[] minLeft = new int[n];
    int[] minRight = new int[n];
    minLeft[0] = arr.get(0);
    minRight[n - 1] = arr.get(arr.size() - 1);

    //find min from left
    for (int i = 1; i < n; i++) {
        minLeft[i] = Math.min(arr.get(i), minLeft[i - 1]);
    }
    // find min from right
    for (int i = n - 2; i >= 0; i--) {
        minRight[i] = Math.min(arr.get(i), minRight[i + 1]);
    }

    long sum = Integer.MAX_VALUE;
    int flag = 0;
    for (int i = 1; i < n - 1; i++) {
        if (minLeft[i - 1] < arr.get(i) && minRight[i + 1] < arr.get(i)) {
            sum = Math.min(sum, minLeft[i - 1] + arr.get(i) + minRight[i + 1]);
            flag = 1;
        }
    }
    if (flag == 0) return -1;
    return sum;

}

}