在数组中找到两个非相邻元素，使它们的和最小。

Question

简介：就我所知，这个问题在SO上还没有被问过。
这是一个面试题。
我甚至不特别寻找代码解决方案，任何算法/伪代码都可以。

---

问题：给定整数数组int[] A和其大小N，找到两个非相邻元素（不能在数组中相邻）且它们的和最小。答案也不能包含第一个或最后一个元素（索引为0和n-1）。此外，解决方案的时间复杂度和空间复杂度应为O(n)。

例如，当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)

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

最后，我想到了一个方法，就是找到数组中除第一个和最后一个元素外的3个最小数，因为其中的两个必须不相邻，所以答案一定是它们之一。但是这个方法也失败了，比如对于A = [2, 2, 1, 2, 4, 2, 6]，-> 2+1=3，虽然我可以找到2, 1, 2，但是不能保证它们分别在索引1, 2, 3处，所以这个方法不一定可行（如果我能确切地找到索引5处的2，那么就可以行得通，但是很遗憾我无法保证）。

---

问题： 现在我陷入了困境，有人能想出一个可行的解决方案/想法吗？

- Idos

---

你确定这个问题可以在O(n)时间内解决吗？ - Matthew D

如何修改三个最小数的方法，以包括索引。您需要6个位置来存储-3个索引，3个值。如果您看到重复的值，则只需更新索引，以便在您的示例中，在看到索引为“5”的“2”时，第二个索引可以更新为5，从而使元素在“2”和“5”处成为同一次遍历的解决方案。只要确保仅在正在跟踪的那些相邻的情况下才为重复项更新索引。 - Ravindra HV

为确保我理解问题，a) A = {1,2,2,2,1} 的答案是4吗？b) 数组的最小长度为5吗？ - Ravindra HV

A) 是的。 B) 是的，否则它就不是真正有趣的了... - Idos

你可能可以使用 Kadane 算法 的变种来解决这个问题。 - higuaro

@higuaro，我认为这需要很多变化，因为该算法严重依赖于所选元素相邻，而这里的要求则相反。 - trincot

Answer 1

这里是一个实时的JavaScript算法实现，它可以：

• 找到最小的4个元素（不包括搜索中的第一个/最后一个元素）
• 找出这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>

该算法有几个循环，其时间复杂度如下：

- 查找4个最小值：O(n)，因为内部循环最多运行3次，即O(1) - 查找非相邻对的最小总和具有双重循环：总体来说，该循环最多运行4次= O(1)。注：可能存在6种可能的对数，但执行保证会更早地退出循环。

因此，该算法的时间复杂度为O(n)。

- trincot

Answer 2

1. 找出除第一个和最后一个数外的最小数。

2. 找出第二小的数，该数不是第一个数的相邻数，也不是数组中的第一个或最后一个数。然后求它们的和。

   • 如果第一个元素是第二个元素或倒数第二个元素，则已经有解决方案了。

3. 否则计算第一个数字的两个邻居的和。检查它是否小于第一个和

   • 如果不是：取第一个和
   • 否则，取第二个和

这将始终起作用，因为如果第一个总和不是答案，那么意味着第一个数字不能成为解决方案的一部分。而另一方面，这意味着解决方案只是第二个总和。

- RomCoo

---

这里缺少一个重要的元素，即在步骤2和3中排除两端。但是，如果您将两端都作为步骤0删除（并将步骤1中的所有元素考虑在内），那么一切都应该正常工作。 - Michael Anderson

我把你的建议添加到了答案中。 - RomCoo

Answer 3

这个问题可以用大约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;
    }
}

- yaskovdev

---

最准确和最优化的解决方案。 - MD Ruhul Amin

Answer 4

我认为这不需要深入推理，可以在一次遍历中解决，保持迄今处理的数组元素的最优解：

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};
}

这里是一些测试代码，包含原帖中提到的边界情况：

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.");
}

- meriton

---

你好，能否请您解释一下这个解决方案是如何满足索引不相邻的要求的？我不明白您在代码中是如何跟踪此问题的。谢谢。 - user2193008

Answer 5

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

- David Eisenstat

---

我正在编写一些代码来测试这个。如果正确的话，太棒了！ :) - Idos

我们是否需要跟踪索引来避免另一个操作？ - Ravindra HV

@RavindraHV 是的，这也是提问者尝试解决方案中隐含的。 - David Eisenstat

如果你将这些数字称为1、2、3、4，那么最小的和是1+2（如果不相邻），否则是1+3（如果不相邻），否则是2+3。1+4都是不相邻的，最优结果是较小的总和。 - gnasher729

Answer 6

使用动态规划。

1. 删除或忽略数组的第一个和最后一个元素。由于它们不能参与解决方案，所以它们不重要。一旦完成这个步骤，您也可以忽略“不得是第一个或最后一个元素”的限制，因为我们已经考虑过了。

2. 找到（剩下的）数组的前三个元素的解决方案（而不考虑“没有第一个/最后一个元素”规则）。在这种情况下只有一个解决方案（`array [0] + array [2]`），因此这是一个微不足道的步骤。

3. 记住不是最后一个元素的最小元素（即`min（array [0]，array [1]）`）。

4. 找到前四个元素的解决方案。我们不必重新解决整个问题；相反，我们只需要询问是否引入第四个元素能够产生更小的解决方案。我们可以通过将第四个元素添加到我们在上一步中备忘的最小元素中，并将总和与我们在第二步中找到的解决方案进行比较来做到这一点。

5. 更新备忘录中的最小元素，使其成为前三个元素中的最小值。

6. 以这种方式继续扩大和更新，直到考虑整个数组。

整个算法的时间复杂度为O（n），因为扩大和更新都是常数时间操作。该算法可以通过简单的归纳证明其正确性。由于我们必须考虑数组的每个元素，所以O（n）也是一个下限，因此该算法是最优的。

- Kevin

---

符合 OP 约束条件的最小数组长度为 5。但这不应影响您的一般方法。 - Reti43

这将meriton的方法用一些流行语言描述出来。 - greybeard

Answer 7

算法：

1. 查找最小值，避免末尾索引。（1 O(n) 次遍历）
2. 查找最小值，避免末尾索引以及（1）的索引和相邻索引。（1 O(n) 次遍历）
3. 查找最小值，避免末尾索引以及（1）的索引。（1 O(n) 次遍历）
4. 查找最小值，避免末尾索引以及（3）的索引和相邻索引。（1 O(n) 次遍历）
5. 返回 (1)+(2) 和 (3)+(4) 中的最小值，如果存在。

第3、4次遍历是为了通过找到两个 2 来处理 [4, 2, 1, 2, 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

- rgettman

Answer 8

我不确定我的解决方案是否正确，因为我只是根据原始问题中的数据进行了测试，而且我也不知道这是否比其他想法更好或更糟，但我想尝试一下。

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}

看起来还不错。

- StepTNT

Answer 9

编辑：你说得对，我完全忽略了相邻的限制条件。 幸运的是，我想到了一个解决方案。 算法如下：

1. 你首先遍历一次数组以找到最小值（O(n)）
2. 然后再遍历一次以找到第二小的值（O(n)）
3. 如果第二小的值不与最小值相邻，则完成（O(1) - 只需检查索引）
4. 否则再遍历一次以找到第三小的值（仍为O(n)）
5. 如果第三小的值与最小值不相邻，则返回最小值和第三小的值，否则返回第二小和第三小的值

- Ilan Kutsman

---

在 StackOverflow 上，仅提供链接的答案是没有帮助的——更不用说由于限制条件，这并没有解决我的问题。请重新阅读问题。 - Idos

OP已经尝试过这种方法，但对于数组A = [2, 2, 1, 2, 4, 2, 6]并不一定有效。 - David Yee

Answer 10

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

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

解决方案为（0,1）或（0,2）或（0,3）或（1,2）或（1,3）或（2,3），其中的值表示数组中跟踪实际元素位置的数组的索引。

此外，您还需要处理长度小于5的特殊情况（arr\[1]+arr[3]），并针对那些小于5的数组提供错误提示。

- Ravindra HV