0

我对应该是一个非常简单的算法有疑问，但由于某种原因，我的头脑无法正常工作（工作太多？）

我有一个数值数组： [ 10, 20, 30, 40, 100, 1000, 5000, 100000] 我想检查数组中的下一个“项目”。

例如，

  • 给定数字 10，我的算法应该返回 10。
  • 给定数字 1，我的算法应该返回 10
  • 给定数字 50，我的算法应该返回 100。
  • 给定数字 99999999，我的算法应该返回 100000

在伪代码中，我在想：

for previousValue, nextValue in values: 
  if ( previousValue < value && nextValue >= value ):
    return nextValue
return values[max]

如果有人能指出我疲惫的大脑我错过了什么，那就太好了。谢谢！

4

4 回答 4

0

我可能会将这个数组表示为一棵树。为了找出最接近的最大值，我将像查找键一样在树中查找，并始终跟踪我最接近的值。当我到达节点的末尾时，我返回最接近的值。

与其他答案相比，这是另一种选择。你可以在这个线程中检查它如何在二叉搜索树中找到最接近给定键值的元素？

于 2013-10-09T08:23:28.263 回答
0

假设数组已经排序，您的解决方案可以正常工作。但为了更清楚，我将其重写如下：

  prev = 0
  for(v in values){
        if(target > prev && target <= v) 
              return v
        prev = v
  }
  return values[values.length-1]
于 2013-10-09T05:39:43.300 回答
0

数组不需要排序。对数组进行排序具有 O(nlogn) 时间复杂度。您可以在 theta(n) 时间内检查数组中的每个元素。

假设数组为arr且比较项为item且数组arr包含至少一个大于或等于 的元素item：

在java中

public static int find_greater(int[] arr,int item)
{
    int j=0;
    int previous =0;
    for(int i=0;i<arr.length;i++){
        if(arr[i]>=item){
            if(j==0){
                previous = arr[i];

             }else{
                 if(arr[i]<previous)
                 {
                     previous = arr[i];
                 }
             }
             j++;

        }
    }
    return previous;
}

在这里，我遍历数组并保留一个变量，该变量previous是大于或等于的最小数字item。此过程的运行时间是theta(N)其中 N 是arr.length。

于 2013-10-09T06:16:27.253 回答
0

在红宝石中：

find 0,values.length,val
def find left,right,val
    if left == right || left > right then return values[left]
    if val > values[(right + left)/2]
        find (right + left)/2, right, val
    else
        find left, (right + left)/2, val
    end
end
于 2013-10-09T05:53:49.940 回答