檢查的一對值是否處於範圍之間從範圍

的陣列可以說所述一對值是：5和10檢查的一對值是否處於範圍之間從範圍

而且

範圍R的陣列是： R = {（6,10），（5,7），（6,9），（4,12）}

在這種情況下，它應該返回4和12之間True因爲5和10都位於。

在O(N)中有一個非常簡單的解決方案，通過在每一對上進行迭代，這可以通過基於R中的一對值的第一個值來對範圍R進行排序來進一步改進（儘管我猜測排序會使最壞情況O（ n log n））。但是，問題是我需要找到多個值對的答案。我正在尋找更好的解決方案，可能以某種方式使用map，這樣可以減少重新計算某些值的需求。基本上，是否有使用動態編程的方法？

任何想法？代碼也將讚賞：P

來源

2016-10-03 SinByCos

您可能對細分樹感興趣。 –

這個問題還不夠清楚。請舉一個更具體的例子。你是否希望這兩個元素都在一個特定的範圍內？這一對是否代表一個範圍？對於範圍（1,4），（7,9）對（3,8）的結果是什麼？爲什麼？ –

我認爲這足夠清楚了嗎？這應該返回false，因爲沒有3和8所在的範圍。 @一個。 – SinByCos

如果你想使用地圖，一個解決方案是創建一個地圖的地圖，一個用於最小值，一個用於最大值。這將需要一些預處理時間，但總體而言，它會更快，因爲通過許多查找長期分攤成本。

你基本上建立一個地圖，對每個有效最小鍵，並且每個值與該mimumum每一個有效的最大鍵地圖..

例如（注意，內未經檢驗的背OF-信封代碼）：

// Psuedo-ish C++11 

typedef std::map<int, std::vector<R>> MaxMap; 
typedef std::map<int, MaxMap> MinMap; 

MinMap minMap; 

// Build maps 
for(range : R) 
{ 
    for(int i=range.min; i<=range.max; ++i) 
    { 
     MaxMap& maxMap = minMap[i]; 
     for(int j=range.min; j<=range.max; ++j) 
     { 
      // We just need some value in the map, 
      // so might as well store a list of the original ranges.. 
      mapMap[j].push_back(range); 
     } 
    } 
}

然後進行查找你把你的最小值，並在MinMap看看它，然後看看你最大的MaxMap。請記住，MinMap給你所有的有效最大值對於任何給定的最低，然後你在MaxMap查找告訴你，如果你的最大的是給定的最低有效的最高...

bool isValidRange(int min, int max) 
{ 
    MinMap::iterator minIt = minMap.find(min); 
    if(minIt == minMap.end()) 
    { 
     return false; 
    } 
    MaxMap& maxMap = minIt->second; 
    MaxMap::iterator maxIt = maxMap.find(max); 
    if(maxIt == maxMap.end()) 
    { 
     return false; 
    } 

    return true; 
}

當然，這只是適用於自然數字。如果您需要負值或範圍內的負值或實數值，您需要其他值...

來源

2016-10-03 17:27:45 BrandonL

檢查的一對值是否處於範圍之間從範圍

回答

相關問題