在总和最小的数组中查找两个非后续元素

Question

简介：据我所知，这个问题还没有在 SO 中提出。
这是一道面试题。
我什至没有专门寻找代码解决方案，任何 algorithm/pseudocode 都可以。

问题：给定一个整数数组int[] A及其大小N，找出2个非后续 （不能在数组中相邻）具有最小总和的元素。此外，答案不得包含第一个或最后一个元素（索引 0 和 n-1）。此外，解决方案应在 O(n) 时间和 space 复杂度内。

例如当 A = [5, 2, 4, 6, 3, 7] 时答案是 5，因为 2+3=5.
当 A = [1, 2, 3, 3, 2, 1] 时答案是 4，因为 2+2=4 并且您不能选择 1 中的任何一个，因为它们位于数组的末尾。

尝试：一开始我以为其中一个的解一定是数组中最小的一个（除了第一个和最后一个），但这很快被反例反驳
A = [4, 2, 1, 2, 4] -> 4 (2+2)

然后我想如果我在数组中找到2个最小的数字（除了第一个和最后一个），解决方案就是这两个。这显然很快就失败了，因为我不能选择 2 个相邻的数字，如果我必须选择不相邻的数字，那么这就是问题的定义:)。

最后我想，好吧，我会在数组中找到 3 最小的数字（除了第一个和最后一个），并且解决方案必须是其中两个，因为其中两个具有彼此不相邻。 also failed due to A = [2, 2, 1, 2, 4, 2, 6] -> 2+1=3 ，这似乎有效，因为我会找到 2, 1, 2，但假设我找到 2, 1, 2 在索引 1, 2, 3 中这不会 必然地 工作（如果我在索引 5 中特别找到 2 但我不能保证不幸的是）。

问题： 现在我很困惑，有人能想出一个可行的 solution/idea 吗？

Answer 1

编辑：你是对的，我完全忽略了邻接约束。幸运的是我想到了解决办法。算法是这样的：

你运行一次遍历数组找到最小的(O(n))
你运行第二次求第二小(O(n))
如果第二小的不与最小的相邻，我们就完成了（O(1) - 只是索引检查）
否则运行第三次求第三小（还是O(n)）
如果不相邻于最小的return最小的和第三小的否则 return 第二和第三小

Answer 2

找到四个最小的并考虑这四个中的所有可能性。最小的不与第二小、第三小或第四小中的至少一个相邻；唯一可能更好的其他可能性是第二小和第三小（假设它们不相邻）。

Answer 3

怎么样：您找到 k 最小的数字（或更准确地说是它们的索引）（k 足够大，比方说 10）。可以肯定的是，想要的一对就在他们之间。现在您只需检查可能的 50 对和 select 满足约束的最佳对。

你不需要 10，少一点也行 - 但多于 3 :)

编辑：找到 k 最小的数字是 O(n)，因为你只保留最好的 10 例如在堆中（添加新元素，删除最大值 O(k*logk)=O(1)操作）。

那么就会有一对满足约束条件（不相邻）。同样清楚的是，如果您使用不是来自 k 的元素构建总和，它将大于从那些 k 元素中选择的最佳对。

检查最多 k*k 对也是 O(1)，因此整个运行时间是 O(n).

Answer 4

我认为这应该可行：

找到最小的 3 个元素及其索引。由于它们都不能相邻，因此从中选择 2 个。

如果全部相邻且最小的在中间，则遍历所有元素，找到第4个最小的元素，取min1+min4、min2+min3中的最小者更小。

您也可以在一次迭代中完成此操作。

Answer 5

算法：

找到最小值，避免结束索引。 (1 O(n) 遍)
找到最小值，避免结束索引和 (1) 的索引以及相邻索引。 (1 O(n) 遍)
找到最小值，避免结束索引和 (1) 的索引（1 O(n) pass）
找到最小值，避免结束索引和(3) 的索引以及相邻索引。 (1 O(n) 遍)
Return 总和 (1) + (2), (3) + (4) 中的最小值（如果存在）。

第 3 步和第 4 步旨在通过找到两个 2 来通过案例 [4, 2, 1, 2, 4] = 4。

public static int minSumNonAdjNonEnd(int[] array)
{
    // 1. Find minimum
    int minIdx1 = -1;
    int minValue1 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if (array[i] < minValue1)
        {
            minIdx1 = i;
            minValue1 = array[i];
        }
    }
    // 2. Find minimum not among (1) or adjacents.
    int minIdx2 = -1;
    int minValue2 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if ((i < minIdx1 - 1 || i > minIdx1 + 1) && (array[i] < minValue2))
        {
            minIdx2 = i;
            minValue2 = array[i];
        }
    }
    boolean sum1Exists = (minIdx1 > -1 && minIdx2 > -1);
    int sum1 = minValue1 + minValue2;

    // 3. Find minimum not among (1).
    int minIdx3 = -1;
    int minValue3 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if ((i != minIdx1) && (array[i] < minValue3))
        {
            minIdx3 = i;
            minValue3 = array[i];
        }
    }

    // 4. Find minimum not among(3) or adjacents.
    int minIdx4 = -1;
    int minValue4 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if ((i < minIdx3 - 1 || i > minIdx3 + 1) && (array[i] < minValue4))
        {
            minIdx4 = i;
            minValue4 = array[i];
        }
    }
    boolean sum2Exists = (minIdx3 > -1 && minIdx4 > -1);
    int sum2 = minValue3 + minValue4;

    if (sum1Exists)
    {
        if (sum2Exists)
            return Math.min(sum1, sum2);
        else
            return sum1;
    }
    else
    {
        if (sum2Exists)
            return sum2;
        else
            throw new IllegalArgumentException("impossible");
    }
}

这会执行 4 次线性搜索，复杂度为 O(n)。

测试用例：

System.out.println(minSumNonAdjNonEnd(new int[] {5, 2, 4, 6, 3, 7}));
System.out.println(minSumNonAdjNonEnd(new int[] {1, 2, 3, 3, 2, 1}));
System.out.println(minSumNonAdjNonEnd(new int[] {4, 2, 1, 2, 4}));
System.out.println(minSumNonAdjNonEnd(new int[] {2, 2, 1, 2, 4, 2, 6}));
System.out.println(minSumNonAdjNonEnd(new int[] {2, 2, 3, 2}));

5
4
4
3
Exception in thread "main" java.lang.IllegalArgumentException: impossible

Answer 6

这是算法的实时 javascript 实现：

找到 4 个最小的元素（从搜索中排除 first/last 元素）
找出原数组中不相邻的这4个元素对
从这些对中找到总和最小的一对

function findMinNonAdjacentPair(a) {
    var mins = [];
    
    // quick exits:
    if (a.length < 5) return {error: "no solution, too few elements."};
    if (a.some(isNaN)) return {error: "non-numeric values given."};
    
    // collect 4 smallest values by their indexes    
    for (var i = 1; i < a.length - 1; i++) { // O(n)
        if (mins.length < 4 || a[i] < a[mins[3]]) {
            // need to keep record of this element in sorted list of 4 elements
            for (var j = Math.min(mins.length - 1, 2); j >= 0; j--) { // O(1)
                if (a[i] >= a[mins[j]]) break;
                mins[j+1] = mins[j];
            }
            mins[j+1] = i;
        }
    }
    // mins now has the indexes to the 4 smallest values

    // Find the smallest sum
    var result = {
        sum: a[mins[mins.length-1]]*2+1 // large enough
    }
    
    for (var j = 0; j < mins.length-1; j++) { // O(1)
        for (var k = j + 1; k < mins.length; k++) {
            if (Math.abs(mins[j] - mins[k]) > 1) { // not adjacent
                if (result.sum    > a[mins[j]]+a[mins[k]]) {
                    result.sum    = a[mins[j]]+a[mins[k]];
                    result.index1 = mins[j];
                    result.index2 = mins[k];
                };
                if (k < j + 3) return result; // cannot be improved
                break; // exit inner loop: it cannot bring improvement
            }
        }
    }
    return result;
}

// Get I/O elements
var input = document.getElementById('in');
var output = document.getElementById('out');
var select = document.getElementById('pre');

function process() {
    // translate input to array of numbers
    var a = input.value.split(',').map(Number);
    // call main function and display returned value
    output.textContent = JSON.stringify(findMinNonAdjacentPair(a), null, 4);
}

// respond to selection from list
select.onchange = function() {
    input.value = select.value;
    process();
}

// respond to change in input box
input.oninput = process;

// and produce result upon load:
process();

Type comma-separated list of values (or select one):</br>
<input id="in" value="2, 2, 1, 2, 4, 2, 6"> &lt;=
<select id="pre">
    <option value="5, 2, 4, 6, 3, 7">5, 2, 4, 6, 3, 7</option>
    <option value="1, 2, 3, 3, 2, 1">1, 2, 3, 3, 2, 1</option>
    <option value="4, 2, 1, 2, 4">4, 2, 1, 2, 4</option>
    <option value="2, 2, 1, 2, 4, 2, 6" selected>2, 2, 1, 2, 4, 2, 6</option>
</select>
</br>
Output:</br>
<pre id="out"></pre>

该算法有几个循环，具有以下大 O 复杂性：

找4个最小的值：O(n)，因为内循环最多运行s 3次，也就是O(1 )
找到非相邻对的最小和有一个双循环：主体总共运行最多 4 次 = O(1)。注意：可能的对数是 6，但保证执行会更快地跳出循环。

所以算法运行s 在 O(n).

Answer 7

详细说明答案，您需要修改插入排序来跟踪最小的四个值和相应的索引（每个索引包含 4 个元素的数组）。

一旦找到，解决方案将是第一对索引差异大于 1 且总和最小的对。

解决方案是 (0,1) 或 (0,2) 或 (0,3) 或 (1,2) 或 (1,3) 或 (2,3) 之一，其中值表示数组的索引依次跟踪数组中实际元素的位置。

您还需要处理数组长度 5 (arr\[1]+arr[3]) 的特殊情况以及小于 5.

的数组的错误

Answer 8

找出第一个和最后一个旁边的最小数字。
找到第二小的，它不是第一个的邻居，也不是数组中的第一个或最后一个。然后求和。
- 如果第一个元素是第二个或倒数第二个元素，那么您已经有了答案。
否则计算第一个数的两个邻居的和。检查它是否小于第一个总和
- 如果不是：取第一个和
- 否则取第二个

这将始终有效，因为如果第一个总和不是答案，则意味着第一个数字不能成为解决方案的一部分。另一方面意味着，解决方案可以只是第二个总和。

Answer 9

我不知道我的解决方案是否正确，因为我只是用 OP 中的数据对其进行了测试，我什至不知道这比其他想法更好还是更差，但我想尝试一下.

static void printMinimalSum(int[] A) {  
    // Looking for mins so we init this with max value
    int[] mins = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
    // Indices, used just to print the solution
    int[] indices = new int[]{-1, -1, -1};
    // If the array has length 5 then there's only one solution with the 2nd and 4th elements
    if (A.length == 5) {
        mins[0] = A[1];
        indices[0] = 1;
        mins[1] = A[3];
        indices[1] = 3;
    } else {        
        // Loop on the array without considering the first and the last element
        for (int i = 1; i < A.length - 1; i++) {
            // We consider each element which is smaller than its neighbours
            if ((i == 1 && A[i] < A[i + 1]) // 1: first element, compare it with the second one
                    || (i == A.length - 2 && A[i] < A[i - 1]) // 2: last element, compare it with the previous one
                    || (A[i] < A[i + 1] && A[i] < A[i - 1])) { // 3: mid element, compare it with both neighbors
                // If the element is "legal" then we see if it's smaller than the 3 already saved
                if (A[i] < mins[0]) {
                    mins[0] = A[i];
                    indices[0] = i;
                } else if (A[i] < mins[1]) {
                    mins[1] = A[i];
                    indices[1] = i;
                } else if (A[i] < mins[2]) {
                    mins[2] = A[i];
                    indices[2] = i;
                }
            }
        }
    }     
    // Compute the 3 sums between those 3 elements
    int[] sums = new int[]{Math.abs(mins[0]+mins[1]), Math.abs(mins[0]+mins[2]), Math.abs(mins[1]+mins[2])};
    // Find the smaller sum and print it
    if (sums[0] < sums[1] || sums[0] < sums[2]){
        System.out.println("Sum = " + sums[0] + " (elements = {" + mins[0] + "," + mins[1] + "}, indices = {" + indices[0] + "," + indices[1] + "}");
    } else if (sums[1] < sums[0] || sums[1] < sums[2]){
        System.out.println("Sum = " + sums[1] + " (elements = {" + mins[0] + "," + mins[2] + "}, indices = {" + indices[0] + "," + indices[2] + "}");
    } else {
        System.out.println("Sum = " + sums[2] + " (elements = {" + mins[1] + "," + mins[2] + "}, indices = {" + indices[1] + "," + indices[2] + "}");
    }
}

public static void main(String[] args) {
    printMinimalSum(new int[]{5, 2, 4, 6, 3, 7});
    printMinimalSum(new int[]{1, 2, 3, 3, 2, 1});
    printMinimalSum(new int[]{4, 2, 1, 2, 4});
    printMinimalSum(new int[]{2, 2, 1, 2, 4, 2, 6});
}

输出为：

Sum = 5 (elements = {2,3}, indices = {1,4}
Sum = 4 (elements = {2,2}, indices = {1,4}
Sum = 4 (elements = {2,2}, indices = {1,3}
Sum = 3 (elements = {1,2}, indices = {2,5}

看起来不错。

Answer 10

我觉得这个不需要什么深层次的推理，可以一次解决，保持目前处理的数组元素的最优解：

public static int[] minimumSumOfNonAcjacentElements(int[] a) {
    // the result for the sequence a[1:i]
    int minSum = Integer.MAX_VALUE;
    int minSumElement1 = Integer.MAX_VALUE;
    int minSumElement2 = Integer.MAX_VALUE;

    // the minimum element eligible for joining with a[i], i.e. from a[1 : i-2]
    int minElement = a[1];

    int prevElement = a[2]; // a[i - 1]
    for (int i = 3; i + 1 < a.length; i++) {
        int sum = minElement + a[i];
        if (sum < minSum) {
            minSum = sum;
            minSumElement1 = minElement;
            minSumElement2 = a[i];
        }

        if (prevElement < minElement) {
            minElement = prevElement;
        }
        prevElement = a[i];
    }

    return new int[] {minSumElement1, minSumElement2};
}

这是一些测试代码，其中包含来自 OP 问题的极端情况：

private static void test(int minSumIndex1, int minSumIndex2, int... input) {
    int[] result = minimumSumOfNonAcjacentElements(input);
    if (result[0] == minSumIndex1 && result[1] == minSumIndex2) {
        // ok
    } else {
        throw new AssertionError("Expected: " + minSumIndex1 + ", " + minSumIndex2 + ". Actual=" + Arrays.toString(result));
    }
}

public static void main(String[] args) throws Exception {
    test(2, 2, 4, 2, 1, 2, 4);
    test(1, 2, 2, 2, 1, 2, 4, 2, 6);
    test(1, 2, 0, 2, 1, 2, 4, 2, 0);
    System.out.println("All tests passed.");
}

Answer 11

使用动态规划。

删除或忽略数组的第一个和最后一个元素。由于他们不能参与解决，所以他们并不重要。完成此操作后，您还可以忽略 "must not be the first or last element" 约束，因为我们已经考虑过了。
找到数组（剩下的）前三个 元素的解（不考虑 "no first/last element" 规则）。在这种情况下只有一个解决方案 (array[0] + array[2])，因此这是一个微不足道的步骤。
记忆不是最后一个元素的最小元素（即min(array[0], array[1])）。
求出前四个元素的解。我们不必重做整个问题；相反，我们只需要问引入第四个元素是否能让我们产生一个更小的解决方案。我们可以通过将第四个元素添加到我们在上一步中记住的最小元素，并将总和与我们在第二步中找到的解决方案进行比较。
更新记忆的最小元素，使其成为前三个元素中的最小值。
以这种方式继续扩大和更新，直到我们考虑了整个数组。

整个算法是O(n)，因为加宽和更新都是常数时间操作。可以通过简单的归纳证明该算法是正确的。 O(n) 也是一个下界，因为我们必须考虑数组的每个元素，所以这个算法是最优的。

Answer 12

我已经用动态规划解决了

我的想法是首先创建一个数组来跟踪迄今为止找到的最小值，如下所示：输入数组 = [1, 3, 0, 5, 6] 最小数组 = [1, 1, 0, 0, 0]

现在使用最小数组和我们可以在下面使用的输入数组：

DP[i] = min(DP[i-1], min(first_data, second_data))

其中 DP[i] 表示到目前为止找到的最小值，它是前两个替代元素的总和。

first_data = 输入数组中 current 个元素的总和 + 最小数组中 current-2 个元素的总和

second_data = 输入数组中 current-1 个元素的总和 + 最小数组中 current-3 个元素的总和

    import random
    def get_min(numbers):
            #disregard the first and last element
            numbers = numbers[1:len(numbers)-1]
            #for remembering the past results
            DP = [0]*len(numbers)
            #for keeping track of minimum till now found
            table = [0]*len(numbers)
            high_number = 1 << 30

            min_number = numbers[0]
            table[0] = min_number
            for i in range(0, len(numbers)):
                    DP[i] = high_number
            for i in range(1, len(numbers)):
                    if numbers[i] < min_number:
                            min_number = numbers[i]
                            table[i] = numbers[i]
                    else:
                            table[i] = min_number
            for i in range(0, len(numbers)):
                    min_first, min_second = high_number, high_number
                    if i >= 2:
                            min_first = numbers[i] + table[i-2]
                    if i >= 3:
                            min_second = numbers[i-1] + table[i-3]
                    if i >= 1:
                            DP[i] = min(min(DP[i-1], min_first), min_second)
            return DP[len(numbers)-1]

    input = random.sample(range(100), 10)
    print(input)
    print(get_min(input))

Answer 13

这个问题用大约10行Java代码就可以解决。

您可以从一个明显但效率低下的 (O(N^2)) 解决方案开始：

public class Main {

    int solve(int[] array) {
        int answer = Integer.MAX_VALUE;
        for (int i = 3; i < array.length - 1; i++) {
            for (int j = 1; j < i - 1; j++) {
                if (array[i] + array[j] < answer) {
                    answer = array[i] + array[j];
                }
            }
        }
        return answer;
    }
}

但是你会注意到你实际上不需要内部 for 循环，因为你可以只保留最小值并在必要时用每个新元素更新它，这比每次都重新找到最小值要快时间。因此，最终的 O(N) 解决方案如下所示：

public class Main {

    int solve(int[] array) {
        int answer = Integer.MAX_VALUE;
        int min = array[1];
        for (int i = 3; i < array.length - 1; i++) {
            min = Math.min(min, array[i - 2]);
            if (array[i] + min < answer) {
                answer = array[i] + min;
            }
        }
        return answer;
    }
}

Answer 14

因为我们只需要跟踪两个不相邻值的最小总和，我们可以通过遍历排除第一个和最后一个元素的数组并跟踪最小值和最小总和来实现。当前最小值将是当前值之前的两个索引。例如，如果我们正在检查当前索引 i，那么 minValue 是从索引 1 到 i-2 的最小值。代码：

    int minSum(int[] A){
        int minSum=Integer.MAX_VALUE;
        int min= Integer.MAX_VALUE;
        for(int i=3; i<A.length-1; i++){
            min= Math.min(A[i-2], min);
            minSum = Math.min(min+A[i], minSum);
        }
        return minSum;
    }

Answer 15

这是 O(N) 时间复杂度的 python 实现

import math

def minSum(array):
    _min = array[1]
    result = math.inf

    for i in range(3, len(array) - 1):
        _min = min(_min, array[i-2])
        if (_min + array[i]) < result:
            result = _min + array[i]
    return result

在总和最小的数组中查找两个非后续元素

Finding two non-subsequent elements in array which sum is minimal

java

arrays

algorithm

minimum

time-complexity