是否有O(n)效率的解决方案来解决以下问题？
您需要在数组中找到一个单元格，使得它之前的所有数字都比它小，而它之后的所有数字都比它大。您应该忽略第一个和最后一个单元格。
例如，请考虑以下列表：
1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11
在这种情况下，答案将是索引为5的数字7。
在数组中查找一个数字
13
- gabi
8
11和11怎么样？ - shmosel
9你尝试过什么？Stack Overflow并不是一个让你向人们寻求解决方案/编写代码的网站。 - Rushy Panchal
@shmosel，请忽略第一个和最后一个数字。 - gabi
4提示：保持一个变量，存储当前符合子列表条件的数字，如果未满足，则为-1，并保持一个变量，存储到目前为止最大的数字。 - Natecat
我觉得这个问题有趣的地方在于大多数情况下根本不存在这样的单元格。一个明显的例子是数字递减的序列，但在随机数组中，我认为机会相当渺茫。因此，“你需要找到”是一个奇怪的提问方式。 - Marc van Leeuwen
显示剩余3条评论
5个回答
31
这里是Python中的一个O(n)、一次遍历的解决方案。将其移植到Java非常简单：
import random
A = [random.randint(1, 10) for i in range(0, 5)] # Generate list of size 5.
max_seen = A[0]
candidate = None
for i in range(1,len(A)):
if candidate is None:
if A[i] > max_seen:
candidate = i
else:
if A[i] <= A[candidate]:
candidate = None
max_seen = max(max_seen, A[i])
print("Given %s " % (A,))
if candidate is not None and candidate != len(A)-1: # Ignore the last element as per spec.
print("found: value=%d; index=%d\n" % (A[candidate], candidate))
else:
print("not found")
你需要运行几次才能生成符合条件的列表。
描述
重新陈述目标：在数组 A 中找到一个元素的索引 i，满足 对于所有 A[j]，j < i => A[j] < A[i] 和对于所有 A[k]，k > i => A[k] > A[i]。第一个这样的元素就是这样的元素，所以我们只需找到第一个。
给定索引 x，如果 x 满足上述条件，则 A[x] > A[0..x-1] and A[x] < A[x+1..A.length]。对于给定的 x，验证这两个约束条件是足够的。注意 A[x] > A[0..x-1] <=> A[x] > max(A[0..x-1])。因此，我们维护迄今为止看到的最大值，找到满足条件 1 的第一个 x，然后迭代遍历数组验证是否满足条件 2。如果条件 2 不被验证，那么我们知道下一个可能的候选者在当前索引 y 之后，因为 A[x..y-1] > A[x] => A[y] < A[x..y-1]，并且大于迄今为止看到的最大值。
- spinkus
4
非常好。由于这只需要一次遍历（和O（1）空间），因此它可以作为“在线算法”完成；您甚至不需要事先知道有多少元素，只需处理一个“迭代器”，并在其“hasNext（）”返回“false”时返回结果即可。 - ruakh
1请将此标记为答案，它只需要循环一次，不需要重复的数组。 - Eric
这个解决方案很有趣，所以我写了一个
c 的实现作为另一个答案，希望你不介意;) - Eric1这是最好的答案。 - Tony Ennis
16
是的，它当然可以在O(n)时间内完成。下面介绍几种方法。
第一种方法更适用于查找所有候选单元格。对数据进行单个O(n)遍历，在每个单元格中设置两个额外的项，因此需要O(n)的空间（许多优化问题可以通过以空间换时间来解决）。
你需要为每个单元格计算出左侧的最高值和右侧的最小值。第一个遍历为除了最后一个单元格之外的所有单元格设置这些项（明显的伪代码）：
# Set current values.
highLeftVal = cell[0]
lowRightVal = cell[cell.lastIndex]
# For running right and left through array.
rightIdx = cell.lastIndex
for each leftIdx 1 thru cell.lastIndex inclusive:
# Left index done by loop, right one manually.
rightIdx = rightIdx - 1
# Store current values and update.
highLeft[leftIdx] = highLeftVal
if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]
lowRight[rightIdx] = lowRightVal
if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]
然后，只需检查每个单元格（除了第一个和最后一个）以确保该值既大于左侧的最高值（根据您的问题，本答案假设“更高/更低”是字面意思，而不是“大于/小于等于”），且小于右侧的最低值：
for each idx 1 thru cell.lastIndex-1 inclusive:
if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]
print "Found value ", cell[idx], " at index ", idx
您可以在下面看到初步处理的结果：
highLeft: - 1 3 3 6 6 7 9 9 10 10
cells : 1 3 2 6 5 7 9 8 10 8 11
lowRight: 2 2 5 5 7 8 8 8 8 11 -
^
在上下两个值有序（不包含）的情况下，唯一一个符合条件的候选单元格是标有^的7。
需要记住的是，这是一个相对容易理解的解决方案，可以找到满足约束条件的多个项目。考虑到您只需要一个项目，可能会获得更好的性能（尽管复杂度仍为O(n)）。
基本思想是从左到右遍历数组，并对每个单元格进行检查，确定左侧所有元素都比其小且右侧所有元素都比其大。
由于从左到右遍历，因此最高的值可以很容易地记住。第二部分似乎涉及到某种未来的判断，但是有一个技巧可以避免这种“时间上的运动”。
这个想法是同时维护当前单元格左侧看到的最高值和答案的索引（最初设置为哨兵值）。
如果当前答案是哨兵值，则选择满足“大于左侧所有元素”的第一个单元格作为可能的答案。
只要情况保持这样，就选择该单元格作为答案。但是，一旦您在其右侧找到一个小于或等于它的单元格，它就不再有效，因此您将放弃它并重新开始搜索。
这种搜索是从当前点而不是从起点开始的，因为：
- 当前答案之后的所有内容（不包括这个（小于或等于）单元格）都高于当前答案，否则您将已经找到一个更小的单元格；并且
- 因此，该单元格必须小于或等于该范围内的每个单元格，因为它小于或等于当前答案；因此
- 在该范围内没有任何单元格是有效的，它们都大于或等于这个单元格。
处理非末端项完成后，您的答案将是哨兵或几乎满足约束条件的单元格。我说“几乎”，因为还需要进行最后一次检查以确保最终项目比其大，因为在遍历过程中未针对该项目执行任何检查。
因此，该算法的伪代码类似于：
# Store max on left and start with sentinel.
maxToLeft = cell[0]
answer = -1
for checking = 1 to cell.lastIndex-1 inclusive:
switch on answer:
# Save if currently sentinel and item valid.
case -1:
if cell[checking] > maxToLeft:
answer = checking
# Set back to sentinel if saved answer is now invalid.
otherwise:
if cell[answer] >= cell[checking]:
answer = -1
# Ensure we have updated max on left.
if cell[checking] > maxToLeft:
maxToLeft = cell[checking]
# Final check against last cell.
if answer != -1:
if cell[cell.lastIndex] <= cell[answer]:
answer = -1
由于我的伪代码（大量）基于Python，因此提供代码实际运行的更具体示例相当简单。首先，是“找到每个可能性”的选项：
cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
highLeft = [0] * len(cell)
lowRight = [0] * len(cell)
highLeftVal = cell[0]
lowRightVal = cell[len(cell)-1]
rightIdx = len(cell) - 1
for leftIdx in range(1, len(cell)):
rightIdx = rightIdx - 1
highLeft[leftIdx] = highLeftVal
if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]
lowRight[rightIdx] = lowRightVal
if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]
print(highLeft)
print(cell)
print(lowRight)
for idx in range(1, len(cell) - 1):
if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
print("Found value", cell[idx], "at index", idx)
第二个选项略微更高效，但只能找到一个可能性：
cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
maxToLeft = cell[0]
answer = -1
for checking in range(1, len(cell) - 1):
if answer == -1:
if cell[checking] > maxToLeft:
answer = checking
else:
if cell[answer] >=cell[checking]:
answer = -1
if cell[checking] > maxToLeft:
maxToLeft = cell[checking]
if answer != -1:
if cell[len(cell] - 1] <= cell[answer]:
answer = -1
if answer == -1:
print ("Not found")
else:
print("Found value", cell[answer], "at index", answer);
print(highLeft)
print(cell)
print(lowRight)
for idx in range(1, len(cell) - 1):
if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
print("Found value", cell[idx], "at index", idx)
这两个例子的输出结果（尽管后一个例子只显示了最后一行）基本上展示了伪代码所要说明的内容：
[0, 1, 3, 3, 6, 6, 7, 9, 9, 10, 10]
[1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
[2, 2, 5, 5, 7, 8, 8, 8, 8, 11, 0]
Found value 7 at index 5
- paxdiablo
3
3根据你对“复杂”的定义，@S.Pinkus。你的定义似乎涉及到最小化通行次数，如果效率是你的首要考虑因素，那么这是可以接受的，但对我来说，代码似乎更难以理解。在其他更强的要求缺失的情况下，我倾向于易于理解的代码 :-) 无论如何，我们两个的答案都是O(n)，因此满足OP的查询，他们可以选择自己喜欢的答案。 - paxdiablo
2@paxdiablo 对我来说，有数据依赖关系的三个循环要难理解得多。我总是对人们看待事情的不同方式感到惊讶，所以各有所好吧。 - spinkus
我会一次性编写这个。函数将是
testCandidate()，acceptCandidate()和removeCandidates()等。 - Tony Ennis5
创建一个附加数组，通过对源数组从左到右进行计算得出。对于该数组中的任何索引N，其值是第一个数组中0:N-1之间观察到的最高值。
int arr1 = new int[source.length];
int highest = MIN_INT;
for (int i = 0; i < source.length; i++) {
arr1[i] = highest;
if (source[i] > highest) {
highest = source[i];
}
}
现在创建第二个数组，通过从右到左扫描来形成，其中索引N处的任何值表示N+1:end之间看到的最低值。
arr2 = new int[source.length];
int lowest = MAX_INT;
for (int i = (source.length-1); i <= 0; i--) {
arr2[i] = lowest;
if (source[i] < lowest) {
lowest = source[i];
}
}
现在您基本上有三个数组：
source: 1 3 2 6 5 7 9 8 10 8 11
arr1: MIN 1 3 3 6 6 7 9 9 10 10
arr2: 2 2 5 5 7 8 8 8 8 11 MAX
现在你只需要一起扫描这三个数组，直到找到一个满足以下条件的索引：
arr1[i] < source[i] < arr2[i]
where:
0 < i < (source.length-1)
代码：
for (int i = 1; i < (source.length-1); i++) {
if ((arr1[i] < source[i]) && (source[i] < arr2[i])) {
return i; // or return source[i]
}
}
这是O(N)时间复杂度。
- selbie
1
1@灰须 - 我们两个在 2 分钟内都提交了答案。我在提交我的答案之后才看到他提交的内容。这在 SO 上有时会发生。昨晚我回来修复代码中的一个错误。 - selbie
3
我使用了S.Pinkus的算法，在c中编写了一个实现，并加入了调试信息。
代码
find_mid_num.c:
/**
* Problem:
* there is an array of number, find an element which is larer than elements before it, and smaller than elements after it,
* refer: https://dev59.com/sVgR5IYBdhLWcg3wd9G5
*
* Solution:
* loop through array, remember max value of previous loopped elements, compare it to next element, to check whether the first condition is met,
* when found an element met the first condition, then loop elements after it to see whether second condition is met,
* if found, then that's it; if not found, say at position 'y' the condition is broken, then the next candidate must be after y, thus resume the loop from element after y,
* until found one or end of array,
*
* @author Eric Wang
* @date 2016-12-23 17:08
*/
#include <stdio.h>
// find first matched number, return its index on found, or -1 if not found,
extern int findFirstMidNum(int *arr, int len);
int findFirstMidNum(int *arr, int len) {
int i=0, j;
int max=arr[0];
while(i < len) {
printf("\n");
if(arr[i] <= max) {
printf("give up [%d]-th element {%d}, 1st condition not met\n", i, arr[i]);
i++;
continue;
}
max = arr[i]; // update max,
printf("checking [%d]-th element {%d}, for 2nd condition\n", i, arr[i]);
j = i+1;
while(j < len) {
if(arr[j] <= max) {
printf("give up [%d]-th element {%d}, 2nd condition not met\n", i, arr[i]);
break;
}
j++;
}
printf("position after 2nd check:\ti = %d, j = %d\n", i, j);
if(j==len && j>i+1) {
return i;
} else {
max = arr[j-1]; // adjust max before jump,
i = j+1; // jump
printf("position adjust to [%d], max adjust to value {%d}, after 2nd check\n", i, arr[j-1]);
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11};
int len = sizeof(arr)/sizeof(arr[0]);
printf("\n============ Input array ============\n");
printf("size:\t%d\n", len);
printf("elements:\t{");
int i;
for(i=0; i<len; i++) {
printf("%d, ", arr[i]);
}
printf("}\n\n");
printf("\n============ Running info ============\n");
int pos = findFirstMidNum(arr, len);
printf("\n============ Final result============\n");
if (pos < 0) {
printf("Element not found.\n");
} else {
printf("Element found at:\n\t position [%d], with value: {%d}\n", pos, arr[pos]);
}
printf("\n");
return 0;
}
编译:
gcc -Wall find_mid_num.c
执行:
./a.out
运行结果:
============ Input array ============
size: 11
elements: {1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11, }
============ Running info ============
give up [0]-th element {1}, 1st condition not met
checking [1]-th element {3}, for 2nd condition
give up [1]-th element {3}, 2nd condition not met
position after 2nd check: i = 1, j = 2
position adjust to [3], max adjust to value {3}, after 2nd check
checking [3]-th element {6}, for 2nd condition
give up [3]-th element {6}, 2nd condition not met
position after 2nd check: i = 3, j = 4
position adjust to [5], max adjust to value {6}, after 2nd check
checking [5]-th element {7}, for 2nd condition
position after 2nd check: i = 5, j = 11
============ Final result============
Element found at:
position [5], with value: {7}
待完成 - 进一步的改进:
- 检查边界元素。
- 提供一个多功能函数来查找所有这样的元素，而不仅仅是第一个。
- Eric
0
这个算法的时间和空间复杂度均为O(n)，只需要一次数组遍历。
逻辑：
- 找到第一个最大值和目前为止找到的最大值，继续遍历数组，直到找到一个小于第一个最大值的值。
- 如果找到了，那么留下第一个最大值和所有在它之前的元素，因为这些元素都比当前找到的元素更大。
- 现在选择一个第一个最大值，使得下一个值应该大于我们一直在寻找的最大值。
代码：
// int[] arr = { 10, 11, 1, 2, 12, 13, 14};
int[] arr = { 1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11};
Integer firstMax = null;
Integer overallMax = null;
for (int i = 1; i < arr.length - 1; i++) {
int currentElement = arr[i];
if (firstMax == null) {
if (overallMax == null) {
firstMax = currentElement;
} else if (overallMax != null && currentElement > overallMax) {
firstMax = currentElement;
}
}
if (overallMax == null || currentElement > overallMax) {
overallMax = currentElement;
}
if (firstMax != null && currentElement < firstMax) {
// We found a smaller element, so all max found so far is useless. Start fresh.
firstMax = null;
}
}
System.out.println(firstMax);
附注：根据我的分析，我认为这应该足够并适用于所有情况。不确定是否有遗漏的情况。
- Kishore Bandi
3
这是错误的。例如，尝试使用
{10, 11, 1, 2, 12, 13, 14}。 - spinkus@S.Pinkus 啊！！好发现。没有想到这种情况。修改了答案。你看到还有其他失败的情况吗？ - Kishore Bandi
我不确定为什么会被踩。有没有任何情况下这个方法不起作用？有人能解释一下吗？ - Kishore Bandi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接