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

Question

简介:据我所知,此问题尚未在SO中提出.
这是一个面试问题.
我甚至没有专门寻找代码解决方案,任何算法/伪代码都可以工作.

---

问题:给定一个整数数组int[] A及其大小N,找到2个非后续(在数组中不能相邻)元素的总和最小.答案也必须不包含第一个或最后一个元素(索引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, 2索引,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>

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

• 找到4个最小值:O(n),因为内循环运行最多3次,即O(1)
• 找到非相邻对的最小总和有一个双循环:总体上最多运行4次= O(1).注意:可能的对数是6,但执行保证会更快地突破循环.

因此算法在O(n)中运行.

Answer 2

1. 找到第一个和最后一个旁边的最小数字.

2. 找到第二个不是第一个的邻居,而不是数组中的第一个或最后一个.然后建立总和.

   • 如果第一个元素是第二个元素或倒数第二个元素,那么您已经有了解决方案.

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

   • 如果不是:拿第一笔钱
   • 否则采取第二个

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

Answer 3

This problem can be solved with about 10 lines of Java code.

You can start with an obvious but inefficient (O(N^2)) solution:

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

But then you can notice that you actually do not need the internal for loop because you can just preserve the minimum and update it with every new element if necessary, which is faster than finding the minimum anew every time. Therefore the final O(N) solution looks like this:

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 4

找到最小的四个,并考虑这四个中的所有可能性.最小的与第二,第三或第四小的至少一个不相邻; 唯一可能更好的其他可能性是第二和第三小(假设它们是不相邻的).

Answer 5

我认为这不需要任何深刻的推理,并且可以在一次通过中解决,保持到目前为止处理的数组元素的最佳解决方案:

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 6

使用动态编程.

1. 删除或忽略数组的第一个和最后一个元素.由于他们无法参与解决方案,因此并不重要.一旦你完成了这个,你也可以忽略"不能是第一个或最后一个元素"的约束,因为我们已经考虑到了它.
2. 找到数组(前面剩下的)的前三个元素的解决方案(并且不考虑"没有第一个/最后一个元素"规则).在这种情况下只有一种解决方案(array[0] + array[2]),所以这是一个微不足道的步骤.
3. 记住不是最后一个元素的最小元素(即min(array[0], array[1])).
4. 找到前四个元素的解决方案.我们不必重做整个问题; 相反,我们只需要问一下,引入第四个元素是否允许我们生成更小的解决方案.我们可以通过将第四个元素添加到我们在上一步中记忆的最小元素,并将总和与我们在第二步中找到的解决方案进行比较来实现.
5. 更新memoized minimal元素,使其成为前三个元素中的最小元素.
6. 继续以这种方式扩展和更新,直到我们考虑整个阵列.

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