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

这是算法的实时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）中 运行。