如何確定一個範圍內的數字？

給定範圍如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

如何確定一個範圍內的數字？

回答

相關問題