5

範囲のリストがあります。各範囲には開始値と終了値があります。つまり、値はその範囲の間にある可能性があります。たとえば、範囲が (1,4) の場合、値は 1、2、3、および 4 になります。ここで、指定された範囲のリストで個別の値を見つける必要があります。以下はサンプルコードです。

class Program
{
    static void Main(string[] args)
    {
        List<Range> values = new List<Range>();
        values.Add(new Range(1, 2));
        values.Add(new Range(1, 3));
        values.Add(new Range(1, 4));
        values.Add(new Range(3, 5));
        values.Add(new Range(7, 10));
        values.Add(new Range(7, 8));

        // Expected Output from the range of values
        //1,2,3,4,5,7,8,9,10
    }
}
class Range
{
    public Range(int _form, int _to)
    {
        from = _from;
        to = _to;
    }
    private int from;

    public int From
    {
        get { return from; }
        set { from = value; }
    }

    private int to;

    public int To
    {
        get { return to; }
        set { to = value; }
    }

}

すべての範囲をループして、個別の値を見つけることができます。しかし、誰かが効率的なアプローチを与えることができれば、それは役に立ちます。

4

3 に答える 3

4
  • 間隔の数が少ない場合は、単純なアプローチでうまくいくはずです。
  • ほとんどの間隔が互いに折りたたまれている場合は、それらをマージする予備ステップを実行して、テストの数を減らすことができます
  • 互いに素な間隔の数が多い場合は、間隔ツリーを構築します。これは、Java のコード例を含む記事へのリンクです。
于 2012-08-08T14:39:30.483 に答える
1

_fromとの範囲_toが小さい場合（示されているように1000）、ブール値の配列[1000]を使用できます。着信範囲ごとに、対応する配列要素をtrueに設定します。つまり、Range（3,6）の場合、配列要素3、4、5、および6をtrueに設定します。次に、配列を反復処理して、trueであるすべてのインデックスを出力します。狭い範囲で十分効率的である必要があります。

于 2012-08-08T14:58:36.880 に答える
1

次の解決策を検討してください（完全なコードは記述せず、一般的なルートのみを記述します）。

  • 着信範囲ごとに、MinVal変数とMaxVal変数を調整します-すべての範囲で最小値を保持し、すべての範囲で最大値をそれぞれ保持します
  • 着信範囲の2つのコレクションを作成し、一方の名前Beginsを、もう一方の名前をEnds
  • すべての範囲が収集されたら、両方のコレクションを並べ替えます。Begins値に従って並べ替える必要がfromあり、値に従ってEnds並べ替える必要がありtoます
  • depthカウンタ変数を0に初期化します
  • 初期化BeginPointerしEndPointerて、それぞれのコレクションの最初の要素に
  • ここで重要な部分：現在の値が収集の開始を示しMinValてMaxValいる場合（現在の数はBeginPointer反復値に等しい）-> depth1ずつ増やしてBeginPointer前進する（連続する「開始」に対して繰り返す）場合は、からに反復します。
  • が0より大きい場合depth->ある範囲内にあるため、現在の反復値を出力します
  • 現在の値が収集の終了を示している場合-> depth1ずつ減少します（連続する「終了」に対して繰り返します）

これは、広範囲の値に対しても機能します。最大値が比較的低い場合（つまり、コメントに示されているOPのように1000-他の回答を参照してください）。

于 2012-08-08T14:48:27.140 に答える