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

Question

简介： 就我所能搜索到的而言，尚无此问题。
这是一个面试问题。
我什至没有专门寻找代码解决方案，任何算法/伪代码都可以使用。

问题： 给定一个整数数组int[] A及其大小N，找到2个最小和的 非后续
元素（在数组中不能相邻）。另外，答案中不得包含第一个或最后一个元素（index 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)

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

最后， 我想，好吧，我只会在数组中找到 3个 最小的数字（除了第一个和最后一个），而且解决方案必须是其中的两个，因为其中两个 必须
彼此不相邻。由于，这 也 失败了A = [2, 2, 1, 2, 4, 2, 6] -> 2+1=3，因为它似乎可以工作，因为我会找到2, 1, 2，但是假设我找到了2, 1, 2in索引，1, 2, 3则 不一定
奏效（如果我专门找到了2in索引，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>

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

• 找到4个最小值： O（n） ，因为内部循环最多运行3次，即 O（1）
• 找到不相邻对的最小和有一个双循环：总共身体最多运行4次= O（1） 。注意：可能的对数为6，但是可以保证执行能够更快地脱离循环。

因此，该算法在 O（n）中 运行。