在数组中找到下一个最小值？
在数组中找到下一个最小值？
提问于 2018-05-28 12:37:51
这个问题已经困扰了我一段时间了。基本上，如果你有一个输入数组4，5，2，6，7，1，4和5的下一个最小数字是2，6和7的下一个最小数字是1，我需要识别这些较小的数字。我在时间上有一个明显的n^2解，但我觉得在时间上有一个O(n)解。我需要在右边下一个最小的数字出现时采取行动，并且在右边没有更小的数字的情况下也要采取行动。
我试过考虑动态编程解决方案和数据结构(特别是堆栈)，但我似乎无法同时控制正确性和O(n)时间复杂度，其中之一似乎对我来说是失败的。
有什么帮助吗？
回答 3
Stack Overflow用户
回答已采纳
发布于 2018-05-28 13:05:36
为此，您可以考虑使用堆栈数据结构。我已经用Java实现了它。其思想是将索引推入弹出，当堆栈中的顶部索引值大于数组的当前索引值时，弹出堆栈，并将当前索引处的值分配给弹出的索引位置。
// Java Implementation of the idea
import java.util.Arrays;
import java.util.Stack;
public class NextSmallest{
public static void main(String[] args) {
int [] A = {4, 5, 2, 6, 7, 1};
int [] ret = nextSmallest(A);
System.out.println(Arrays.toString(ret)); // prints [2, 2, 1, 1, 1, 0]
}
static int [] nextSmallest(int [] A) {
Stack<Integer> stack = new Stack<>();
int n = A.length;
int [] nextSmallestIndex = new int[n];
for(int i = 0; i < n; i++) {
while(!stack.isEmpty() && A[stack.peek()] > A[i]) {
nextSmallestIndex[stack.pop()] = A[i];
}
stack.push(i);
}
return nextSmallestIndex;
}
}Stack Overflow用户
发布于 2018-05-28 13:21:16
你如何定义你的起点？如果你知道你想从元素3开始看，或者你想找到一个值，然后从那个值所在的任何元素开始，然后从那里开始？如果没有为数组的其余部分找到一个较低的值，会发生什么？
假设您知道要从数组中的哪个元素开始，只因为我正处于PHP项目的中间。
<?php
// our array of numbers
$array=array(4, 5, 2, 7, 6, 1);
// what index are we starting at?
$start=2;
// what index are we comparing to?
$counter=0;
// some output
print("First value is ".$array[$start]." at array element ".$start);
// while the initial value is less or equal to the compare value, AND
// the compare position is within the bounds of the array
// increment the counter - our comparison isn't lower
while((($start+$counter)<count($array))&&($array[($start)]<=$array[($start+$counter)])){
$counter++;
}
// did we make it through without exceeding bounds of array or not?
if(($start+$counter)<count($array)){
print("\nNext lower value is ".$array[($start+$counter)]." at array element ".($start+$counter));
}else{
print("\nEnd of array reached without finding lower value...");
}
print("\n");
?>Stack Overflow用户
发布于 2018-05-28 16:37:05
使用JavaScript中的优化代码，以O(n)方式找到以下解决方案
var arr = [4, 5, 2, 7, 6, 1, 3, 4];
function getNextSmallestValue(index){
var elemvalue = arr[index];
var minValue = elemvalue;
for(var i=index;i<arr.length;i++){
if(minValue> arr[i]){
minValue = arr[i];
}
if((minValue!==elemvalue && elemvalue<arr[i]) || i === arr.length-1){
return minValue;
}
}
}
console.log(getNextSmallestValue(0)); // 2
console.log(getNextSmallestValue(3)); // 1
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50559195
复制相关文章
相似问题