如何确定一个范围内的数字？

给定范围如0..5 ..... 20 .... 25..40 ... 50 ...... 100，我必须确定一个数字在哪个范围内。所以问题是确定数字在哪个范围内的最快方式是什么，例如，aNum = 56的范围是50 .... 100。在确定范围之后，我会将范围的起始数字分配给aNum，在这种情况下为50。所以在最后，ANUM = 50如何确定一个范围内的数字？

我只是想知道，如果它可以花费一定的时间O（1）它。

任何suggesions将不胜感激。您可以使用任何数据结构来完成它。

来源

2012-10-25 user1687717

所以，你的范围是相同的大小呢？我的建议是使用的情况下的结构，像这样：http://cupsofcocoa.com/2010/11/14/extension-5-the-switch-statement/ – Aquillo

使用的[间隔树（HTTP：// EN .wikipedia.org/wiki/Interval_tree）来存储范围。不是'O（1）'，但搜索将是'O（日志（范围号））'。我不确定IOS，但是boost有很好的间隔树实现。 – Vikas

@Vikas。不是O（1），因为常量时间范围查询不存在。 – UmNyobe

对于所示出的类型的范围（由5整除）下面的算法是好的：

段中所有的范围由5（因此，例如25〜40实际上是3个范围：25-29 ，30-34和35-39。
创建一个查找数组，将关键字段设置为范围，例如，如果范围25-39是＃4，而段25-29是＃15，则30- 34是＃16，35-39是＃17，然后查找[15] = 4，查找[16] = 4，查找[17] = 4等。是分裂的问题。将数字除以5得到D，然后范围＃= lookup [D]。

如果你的范围是不规则的，不能由一个共同的数整除，那么所有可能值的查询表可以在内存作为代价创建。

这是一个线性时间算法。

来源

2012-10-25 15:05:52

假设有N有序范围，目标范围可以在O(Log N)使用二进制搜索算法找到。少于这一点是不可能的。例如，可以考虑其中的所有范围等于诸如壳体：

1..2..3..4.. .. 99..100

在这种情形中，发现目标范围等同于在排序后的数组，其不能在O(1)进行查找的数量。

来源

2012-10-25 15:09:44 RGO

下面是一个示例的算法：

确定每个范围的范围和最小和最大值的数量。
迭代通过所有的范围，并比较数量的最小值和最大值为每个范围。
如果在任何范围内，请将其设置为等于该范围的最小值。
如果它不在任何范围内，请做任何需要的操作。

下面的代码说明用C实现这种算法的一个例子：

#include <stdio.h> 
#include <stdlib.h> 

/*We assume there is a fixed number of ranges*/ 
#define RANGE_COUNT 4 

int main(int argc, char** argv){ 
    /*Set the minimum and maximum values for each range*/ 
    int ranges[RANGE_COUNT][2] = {{0, 5}, {20, 20}, {25, 40}, {50, 100}}; 
    int x = 0, num = 0; 

    /*In this example, we are using the command-line for input*/ 
    if(argc != 2){ 
     fprintf(stderr, "Usage: %s <number>", argv[0]); 
     exit(1); 
    } 

    /*We need to ensure that the input is a number*/ 
    if(!(num = atoi(argv[1])) && argv[1][0] != '0'){ 
     fprintf(stderr, "Error: \"%s\" is not a number", argv[1]); 
     exit(1); 
    } 

    /*See if the number is in any of the ranges*/ 
    for(x = 0; x < RANGE_COUNT; x++){ 
     if(num >= ranges[x][0] && num <= ranges[x][1]){ 
     /*If the number is in a range, say which one it is*/ 
     printf("The number %d is in the range %d..%d\n", 
      num, ranges[x][0], ranges[x][1]); 

     /*Set the number equal to the minimum value of the range it is in*/ 
     num = ranges[x][0]; 
     printf("num = %d\n", num); 
     exit(0); 
     } 
    } 

    /*If the number is not in any of these ranges, indicate that it is not*/ 
    printf("The number %d is not in any of these ranges\n", num); 

    return 0; 
}

来源

2012-10-26 03:14:40

如何确定一个范围内的数字？

回答

相关问题