在数组中找到两个最小的非后续元素 [英] Finding two non-subsequent elements in array which sum is minimal
问题描述
简介：据我所知，还没有有人问这个问题。
这是一个面试问题。
我甚至没有专门寻找代码解决方案，任何算法/伪代码都可以使用。
Intro: As far as I could search, this question wasn't asked in SO yet.
This is an interview question.
I am not even specifically looking for a code solution, any algorithm/pseudocode will work.
问题：给定整数数组 int [] A 及其大小 N ，找到2个非后继（不能在数组中相邻）元素，它们的和最少。另外，答案中不得包含第一个或最后一个元素（索引 0 和 n-1 ）。另外，解决方案还应该是 O（n） 的时间和空间复杂度。
The problem: Given an integer array int[] A and its size N, find 2 non-subsequent (can't be adjacent in the array) elements with minimal sum. Also the answer must not contain the first or last elements (index 0 and n-1). Also the solution should be in O(n) time and space complexity.
例如当 A = [5，2，4，6，3，7] 时，答案为 5 ，因为 2 + 3 = 5 。
当 A = [1、2、3、3、2、1] 的答案是 4 ，因为 2 + 2 = 4 并且您不能选择 1 ，因为数组的末尾。
E.g. when A = [5, 2, 4, 6, 3, 7] the answer is 5, since 2+3=5.
When A = [1, 2, 3, 3, 2, 1] the answer is 4, since 2+2=4 and you can't choose either of the 1's since the are at the ends of the array.
尝试：首先，我认为解决方案中的一个数字必须是数组中最小的数字（除了第一个和最后一个） ），但很快就被反例反驳了
A = [4，2，1，2，2，4] -> 4（2 + 2）
Attempt: At first I thought that one of the numbers in the solution must be the smallest one in the array (besides the first and last), but this was refuted quickly with the counter-example
A = [4, 2, 1, 2, 4] -> 4 (2+2)
然后，我想如果我发现 2 个最小的数字（除了第一个最后）在数组中，解决方案将是这两个。显然这很快就失败了，因为我不能选择2个相邻的数字，而且如果我必须选择非相邻的数字，那么这就是问题的定义：）。
Then I thought that if I find the 2 smallest numbers (besides the first and last) in the array, the solution will be those two. This obviously quickly failed because I can't choose 2 adjacent numbers, and if I have to choose non-adjacent numbers then this is the very definition of the question :).
最后，我想，我会发现数组中的 3 个最小的数字（除了第一个和最后一个），解决方案必须是其中的两个，因为其中两个必须彼此不相邻。
由于 A = [2，2，1，2，4，4，2，6] -> 2 + 1 = 3 ，它似乎起作用，因为我会找到 2，1，2 ，但是假设我正在找到<$ c $索引 1、2、3 中的c> 2、1、2 ，这将不必要有效（它会如果我在索引 5 中特别找到了 2 ，但不幸的是，我无法保证。
Finally I thought, well, I will just find the 3 smallest numbers (besides the first and last) in the array, and the solution will have to be two of those, since two of those have to not be adjacent to each other.
This also failed due to A = [2, 2, 1, 2, 4, 2, 6] -> 2+1=3 , which seems to work because I will find 2, 1, 2, but assuming I am finding the 2, 1, 2 in indexes 1, 2, 3 this won't necessarily work (it would if I found specifically the 2 in index 5 but I can't guarantee that unfortunately).
问题：
现在我很困惑，任何人都可以提出解决方案/想法
Question: Now I'm stumped, can anyone come up with a solution/idea that works?
推荐答案
这是算法的实时javascript实现，
Here is a live javascript implementation of an algorithm that:
- 查找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"> <=
<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复杂度：
The algorithm has a few loops with following big-O complexities:
- 找到4个最小值： O（n），因为内部循环最多运行3次，即 O（1）
- 找出非的最小和-相邻对有一个双循环：总共身体最多运行4次= O（1）。注意：可能的对数为6，但是可以保证执行能够更快地脱离循环。
- find 4 smallest values: O(n), as the inner loop runs at most 3 times, which is O(1)
- find the smallest sum of non-adjacent pairs has a double loop: in total the body will run at most 4 times = O(1). NB: The number of possible pairs is 6, but the execution is guaranteed to break out of the loops sooner.
因此算法可以运行在 O（n）中。
So the algorithm runs in O(n).
这篇关于在数组中找到两个最小的非后续元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
