44

数値が0〜10の間にある場合は0を返し、11〜20の場合は1を返すというユースケースがあります。

0 => 0-3, (0 and 3 are inclusive)
1 => 4-15, (4 and 15 are inclusive)
2 => 16-40, (16 and 40 are inclusive)
3 => 41-88, (41 and 88 are inclusive)
5 => 89-300 (89 and 300 are inclusive)

どうすれば実装できるか考えていて、Javaマップを考えていましたが、範囲検索ができません

私はこのようなものに興味があります、私は機能を持っています

int foo() {

}

fooが5を返す場合、それは0から10の間にあるので、私は0を使用し、fooが25を返す場合、2を使用します。

何か案は

編集：実際には、範囲は0-10、11-20ほど単純ではありません。範囲検索ができるようになりたいです。混乱してすみません。正しい例を追加したクエリに基づいて、数字は連続しています

4

6 に答える 6

93

範囲が均一でなく、「穴」がある、より一般的な問題のいくつかの可能な解決策を考えることができます。最も単純なものは次のとおりです。

  1. 複数のキーを同じ値にマッピングして、すべての有効なキー値のマップにデータを入力するだけです。HashMapsを使用すると仮定すると、これは最も時間効率が良い（O（1）ルックアップ）はずですが、セットアップ時により多くの作業があり、より多くのスペースを使用します。
  2. NavigableMapを使用floorEntry(key)し、を使用してルックアップを実行します。これは時間効率が低くなりますが（O（log（N）ルックアップ）、スペース効率が高くなります。

これは、マッピングに「穴」を許可するNavigableMapsを使用したソリューションです。

private static class Range {
   public int upper, value;
   ...
}

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>();
map.put(0, new Range(3, 0));       // 0..3     => 0
map.put(5, new Range(10, 1));      // 5..10    => 1
map.put(100, new Range(200, 2));   // 100..200 => 2

// To do a lookup for some value in 'key'
Map.Entry<Integer,Range> entry = map.floorEntry(key);
if (entry == null) {
    // too small
} else if (key <= entry.getValue().upper) {
    return entry.getValue().value;
} else {
    // too large or in a hole
}

一方、「穴」がない場合、解決策はより簡単です。

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(0, 0);    // 0..4     => 0
map.put(5, 1);    // 5..10    => 1
map.put(11, 2);   // 11..200  => 2

// To do a lookup for some value in 'key'
if (key < 0 || key > 200) {
    // out of range
} else {
   return map.floorEntry(key).getValue();
}
于 2009-08-21T23:58:36.573 に答える
12

擬似コード：

  1. 範囲の境界をフラット配列に格納しますnew int[] {0, 3, 5, 15, 100, 300}。
  2. 配列に数値を挿入するかのように、配列を二分探索します。を参照してくださいArrays.binarySearch()。
  3. 挿入点が偶数の場合、数値はどの範囲にも収まりません。
  4. 挿入点が奇数の場合、対応する範囲に収まります。たとえば10、上記の配列のの挿入ポイントは、3との間に配置さ5れる15ため、2番目の範囲に属します。
于 2009-08-22T00:04:19.680 に答える
4

算術演算では解決できないより一般的なケースでは、適切なコンパレータを使用してTreeMapを作成できます。境界値のマッピングを追加してから、ceilingEntryまたはfloorEntryを使用して適切な一致を見つけます。

于 2009-08-21T23:52:26.647 に答える
0

私はあなたが望むものはの線に沿ったものだと思いますfoo()/10、しかしそれはあなたがあなたが要求したものからわずかに範囲を外すでしょう。簡単なパターンに従わない場合は、「マップ」内の各アイテムの2つのエンドポイントといつでも比較できます。

于 2009-08-21T23:41:37.747 に答える
0

最も簡単な解決策は、範囲の上限から範囲がマッピングされる値にマッピングを追加し、マッピング（マッピングの上限）に到達するまで数値（マップのキー）を増やし続けることだと思います。あなたの番号が入っている範囲）。

もう1つの方法は、範囲内のすべてのエントリをマップに入力し、それぞれにマッピングを追加することです。

どちらがより効率的かは、範囲内のすべての番号を繰り返し要求する必要があるか（後者のソリューションを使用）、一部の番号だけを数回要求する必要があるか（最初のソリューションを使用）によって異なります。

于 2009-08-22T00:45:17.867 に答える
0

John Kugelmanの回答に基づいて、日付範囲に関連付けられたデータを持つ日付範囲検索に類似したものが必要でした...これは私がそれをどのように適用したかの例です。「dates」がキーになり、「rangeData」が関連付けられたデータになります。

  long[] dates = new long[] {
    Instant.parse("1900-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1950-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1960-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1970-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1980-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1990-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2000-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2010-01-01T00:00:00Z").toEpochMilli()
  };
  String[] rangeData = new String[] {
    "Before 1900 data", "Before 1950 data", "Before 1960 data", 
    "Before 1970 data", "Before 1980 data", "Before 1990 data", 
    "Before 2000 data", "Before 2010 data"
  };
  
  long searchDate = Instant.parse("1949-02-15T00:00:00Z").toEpochMilli();
  int result = Arrays.binarySearch(dates, searchDate);
  
  System.out.println("Result: " + result); 
  if (result == dates.length) {
      System.out.println("Date is after all ranges");
      System.out.println("Data: none");
  }
  else if (result >= 0) {
      System.out.println("Date is an exact match of " + Instant.ofEpochMilli(dates[result]));
      System.out.println("Data: " + rangeData[result]);
  }
  else {
      int resultIndex = Math.abs(result) - 1;
      System.out.println("Date is before idx: "+ resultIndex + " date " + Instant.ofEpochMilli(dates[resultIndex]));
      System.out.println("Data: " + rangeData[resultIndex]);
  }

結果

Result: -2
Date is before idx: 1 date 1950-01-01T00:00:00Z
Data: Before 1950 data
于 2021-01-02T09:02:07.660 に答える