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

Question

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

---

问题:给定一个整数数组int[] A及其大小N , 找到 2 个 non-subsequent(数组中不能相邻)总和最小的元素。答案也不能包含第一个或最后一个元素(索引 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中的任何一个's 因为在数组的末尾。

---

尝试:起初我认为解决方案中的一个数必须是数组中最小的一个(除了第一个最后)，但这很快就被反例驳斥了
A = [4, 2, 1, 2, 4] -> 4 (2+2)

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

最后我想，好吧，我会在数组中找到 3 个最小的数字(除了第一个和最后一个)，并且解决方案必须是两个其中，因为其中两个必须彼此不相邻。 由于A = [2, 2, 1, 2, 4, 2, 6]，此也失败了-> 2+1=3 ，这似乎可行，因为我会找到 2, 1, 2 ，但假设我找到 2, 1, 2在索引中 1, 2, 3这不会必然起作用(如果我在索引 2 中找到了 5 就可以了，但不幸的是我不能保证)。

---

问题: 现在我很困惑，谁能想出一个可行的解决方案/想法？

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>

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

• 找到4个最小值:O(n)，因为内循环最多运行3次，即O(1)
• 找到最小的非相邻对的和有一个双循环:总共 body 最多运行 4 次 = O(1)。注意:可能的对数为 6，但可以保证执行更快地跳出循环。

所以算法在O(n)中运行。