私が思いついたものよりも効率的な解決策があるかどうか知りたいです（まだコード化されていませんが、その要点は下部に記載されています）。
入力として非負の int n と間隔のリスト [[a_1; b_1]; : : : ; [午前; b_m]] を実行し、すべての間隔を繰り返して結合すると、n 番目に小さい数 (0 から始まる) を計算します。たとえば、間隔が [1; 5]; [2; 4]; [7; 9]、繰り返しとの結合は[1; 9]になります。2; 2; 3; 3; 4; 4; 5; 7; 8; 9] (注 2; 3; 4 は [1; 5] と [2; 4] の両方の間隔にあるため、それぞれ 2 回表示されます)。この間隔のリストでは、0 番目に小さい数値は 1 になり、3 番目と 4 番目に小さい数値は両方とも 3 になります。b_i は非常に大きくなる可能性があり (1 兆など)、いくつかの間隔があります。
私が考えた方法は、ユニオン配列を作成してトラバースするという簡単な解決策です。
この問題は、O（N log N）で解決できます。ここで、Nは、間隔のエンドポイントの実際の値に関係なく、リスト内の間隔の数です。
この問題を効率的に解決するための鍵は、重複する可能性のある間隔のリストを、互いに素であるか同一である間隔のリストに変換することです。与えられた例では、最初の間隔のみを分割する必要があります。
{ [1,5], [2,4], [7,9]} =>
+-----------------+ +---+ +---+
{[1,1], [2,4], [5,5], [2,4], [7,9]}
（ただし、これを明示的に行う必要はありません。以下を参照してください。）これで、新しい間隔を並べ替えて、重複をカウントに置き換えることができます。それから、各（おそらく複製された）間隔が表す値の数を計算できます。ここで、値を累積して、ソリューションがどの間隔にあるかを把握する必要があります。
interval count size values cumulative
in interval values
[1,1] 1 1 1 [0, 1)
[2,4] 2 3 6 [1, 7) (eg. from n=1 to n=6 will be here)
[5,5] 1 1 1 [7, 8)
[7,9] 1 3 3 [8, 11)
累積値を半開区間のリストとして記述しましたが、明らかに必要なのはエンドポイントだけです。次に、たとえば、累積値リストを二分探索することによって、どの間隔が値nを保持するかを見つけることができます。また、nから間隔の開始を減算し、次に整数で除算することによって、間隔内のどの値が必要かを判断できます。カウント。
上記の表の最大サイズは、元の間隔の2倍であることは明らかです。これは、すべての行が元のリストのある間隔の開始または終了のいずれかで開始および終了する必要があるためです。間隔を閉じているのではなく半分開いていると書いた場合、これはさらに明確になります。その場合、テーブルの正確なサイズは、エンドポイントのコレクション内の一意の値の数になると断言できます。そして、その洞察から、テーブルはまったく必要ないことがわかります。エンドポイントのソートされたリストが必要です（ただし、各値がどのエンドポイントを表すかを知る必要があります）。探している値に到達するまで、アクティブな間隔の数のカウントを維持しながら、そのリストを単純に繰り返すことができます。
これがPythonの簡単な実装です。改善される可能性があります。
def combineIntervals(intervals):
# endpoints will map each endpoint to a count
endpoints = {}
# These two lists represent the start and (1+end) of each interval
# Each start adds 1 to the count, and each limit subtracts 1
for start in (i[0] for i in intervals):
endpoints[start] = endpoints.setdefault(start, 0) + 1
for limit in (i[1]+1 for i in intervals):
endpoints[limit] = endpoints.setdefault(limit, 0) - 1
# Filtering is a possibly premature optimization but it was easy
return sorted(filter(lambda kv: kv[1] != 0,
endpoints.iteritems()))
def nthSmallestInIntervalList(n, intervals):
limits = combineIntervals(intervals)
cumulative = 0
count = 0
index = 0
here = limits[0][0]
while index < len(limits):
size = limits[index][0] - here
if n < cumulative + count * size:
# [here, next) contains the value we're searching for
return here + (n - cumulative) / count
# advance
cumulative += count * size
count += limits[index][1]
here += size
index += 1
# We didn't find it. We could throw an error
したがって、私が言ったように、このアルゴリズムの実行時間は、間隔の実際の値とは無関係です。間隔リストの長さにのみ依存します。この特定の解決策はO(N log N)、ソートのコスト（in combineIntervals）によるものです。フルソートの代わりに優先キューを使用した場合、ヒープを構築できますO(N)が、スキャンO(log N)されたエンドポイントごとにスキャンを実行します。Nが本当に大きく、引数の期待値nが比較的小さい場合を除いて、これは逆効果になります。ただし、複雑さを軽減する方法は他にもあるかもしれません。
編集2:
これがあなたの質問に対するさらに別の見方です。
間隔をグラフィカルに考えてみましょう。
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
[-------]
[-----------------]
[---------]
[--------------]
[-----]
下限の昇順で並べ替えると、上記の interval list のようなものが得られます([2;10];[4;24];[7;17];[13;30];[20;27])。各下限は、新しい間隔の開始を示し、数値の複製のもう 1 つの「レベル」の開始も示します。逆に、上限はそのレベルの終わりを示し、重複レベルを 1 つ減らします。したがって、上記を次のリストに変換できます。
[2;+];[4;+];[7;+][10;-];[13;+];[17;-][20;+];[24;-];[27;-];[30;-]
最初の値は境界のランクを示し、2 番目の値は境界が下限 ( +) か上限 ( -) かを示します。n 番目の要素の計算は、リストに従い、下限または上限に遭遇したときに重複レベルを上げ下げし、重複レベルをカウント係数として使用することによって行われます。
リストを再びグラフィカルに考えてみましょうが、ヒストグラムとして:
3333 44444 5555
2222222333333344444555
111111111222222222222444444
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
上のビューは最初のビューと同じで、すべての間隔が垂直に詰め込まれています。
1最初のもの、2番目のものなどの要素です2。実際、ここで重要なのは、各インデックスの高さであり、各インデックスがすべての間隔の和集合で複製される回数に対応します。
3333 55555 7777
2223333445555567777888
112223333445555567777888999
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
| | | | | | || | |
ヒストグラム ブロックは区間の下限で始まり、上限または下限の 1 単位前で終了することがわかります。そのため、新しい表記法をそれに応じて変更する必要があります。
n間隔を含むリストを使用して、最初のステップとして、リストを上記の表記 ( O(n) ) に変換し、それを昇順 ( O(nlog(n)) )に並べ替えます。数を計算する 2 番目のステップは、 O (nlog(n) )の合計平均時間に対してO(n) にあります。
これは、'+' と '-' の代わりに1andを使用した、OCaml での簡単な実装です。-1
(* transform the list in the correct notation *)
let rec convert = function
[] -> []
| (l,u)::xs -> (l,1)::(u+1,-1)::convert xs;;
(* the counting function *)
let rec count r f = function
[] -> raise Not_found
| [a,x] -> (match f + x with
0 -> if r = 0 then a else raise Not_found
| _ -> a + (r / f))
| (a,x)::(b,y)::l ->
if a = b
then count r f ((b,x+y)::l)
else
let f = f + x in
if f > 0 then
let range = (b - a) * f in
if range > r
then a + (r / f)
else count (r - range) f ((b,y)::l)
else count r f ((b,y)::l);;
(* the compute function *)
let compute l =
let compare (x,_) (y,_) = compare x y in
let l = List.sort compare (convert l) in
fun m -> count m 0 l;;
注: - 上記の関数は、求められた数が間隔を超えている場合に例外を発生させます。このまれなケースは、以下の他の方法では考慮されていません。- OCaml で使用されるリストの並べ替え関数はマージ 並べ替えであり、これはO(nlog(n))で効果的に実行されます。
編集：
間隔が非常に大きい可能性があることを考えると、最初に示した解決策 (以下を参照) は最適とはほど遠いものです。代わりに、リストを変換することで処理を大幅に高速化できます。重複するものを検索して間隔リストを圧縮し、間隔のプレフィックス、オーバーラップの数倍、間隔のサフィックスを付けることで置き換えます。次に、リストの各要素がカバーするエントリの数を直接計算できます。上記の分割 (プレフィックス、インフィックス、サフィックス) を見ると、処理を行うための最適な構造はバイナリ ツリーであることがわかります。そのツリーのノードには、オプションでプレフィックスとサフィックスを付けることができます。したがって、ノードには以下が含まれている必要があります。
iノードの間隔iリスト内の繰り返し回数を示す整数、i i この構造が整っていると、ツリーは自動的にソートされます。そのツリーを具現化する ocaml タイプの例を次に示します。
type tree = Empty | Node of int * interval * tree * tree
ここで、変換アルゴリズムはツリーの構築に要約されます。
この関数は、そのコンポーネントからツリーを作成します。
let cons k r lt rt =
the tree made of count k, interval r, left tree lt and right tree rt
この関数は、ツリーに区間を再帰的に挿入します。
let rec insert i it =
let r = root of it
let lt = the left subtree of it
let rt = the right subtree of it
let k = the count of r
let prf, inf, suf = the prefix, infix and suffix of i according to r
return cons (k+1) inf (insert prf lt) (insert suf rt)
ツリーが構築されると、ノードのカウントを使用してツリーの事前順序トラバーサルを実行し、n 番目の要素の計算を高速化します。
以下は私の以前の回答です。
私のソリューションの手順は次のとおりです。
dq（またはある時点で逆になるリスト）が必要ですコードは次のとおりです。
let lower i = lower bound of interval i
let upper i = upper bound of i
let il = sort of interval list
i <- 0
j <- lower (head of il)
loop on il:
i <- i + 1
let h = the head of il
let il = the tail of il
if upper h > j then push h to dq
if lower h > j then
il <- concat dq and il
j <- j + 1
dq <- empty
loop
if i = k then return j
loop
このアルゴリズムは、関連する間隔のみを考慮してi、和集合内の要素のランクとその要素の値jの両方をカウントして、単に間隔を反復することによって機能します。目標順位kに達した場合、値を返却します。
複雑さはおおよそ O(k) + O(sort(l)) です。
私があなたの質問を正しく理解していれば、間隔のリストの和集合で k 番目に大きい要素を見つけたいと考えています。リストの数 = 2 であると仮定すると、問題は次のようになります: 2 つの並べ替えられた配列の結合で k 番目に小さい要素を見つけます (区間 [2,5] は 2 から 5 までの要素 {2,3,4,5} に他なりません)。 ) この解は(n+m)log(n+m) 時間 (n と m はリストのサイズ) で解くことができます。i と j はリスト反復子です。
Maintaining the invariant
i + j = k – 1,
If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.
詳細はこちら
問題は、lists=3 リストがない場合です。
Maintaining the invariant
i + j+ x = k – 1,
i + j=k-x-1
The value k-x-1 can take y (size of third list, because x iterates from start point of list to end point) .
problem of 3 lists size can be reduced to y*(problem of size 2 list). So complexity is `y*((n+m)log(n+m))`
If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.
したがって、サイズ n リストの問題の場合、複雑さは NP です。
しかし、はい、k< sizeof(いくつかのリスト) を知っていれば、サイズが k より大きいリストの k+1 番目の要素から最後まで (検索スペースから) 要素を切り刻むことができれば、小さな改善を行うことができます (私はそれだと思いますk が大きい場合は役に立ちません。間違いがある場合はお知らせください。
例を挙げて説明しましょう: これらの区間 [5,12]、[3,9]、[8,13] が与えられたとします。これらの間隔の結合は次のとおりです。
number : 3 4 5 5 6 6 7 7 8 8 8 9 9 9 10 10 11 11 12 12 13.
indices: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
lowest入力に 9 が渡されると、 は 11 を返します。入力に 9 が渡されると、 は 14 を返します
。highest
最低関数と最高関数は、x がその間隔に存在するかどうかを確認するだけです。存在する場合は、xa (間隔の下位インデックス) を追加して、その 1 つの特定の間隔の値を返します。間隔が x よりも完全に小さい場合は、その間隔内の要素の総数を戻り値に追加します。
13 が渡されると、find 関数は 9 を返します。
find 関数は、二分探索の概念を使用して、k 番目に小さい要素を見つけます。指定された範囲 [0,N] で (範囲が指定されていない場合は、O(n) で高い範囲を見つけることができます) 中間を見つけ、中間の最低値と最高値を計算します。指定された k が最低値と最高値の間にある場合は mid を返します。それ以外の場合、k が下半分 (0, mid-1) の最低値以下の場合、それ以外の場合は上半分 (mid+1、high) を検索します。
間隔の数が n で範囲が N の場合、このアルゴリズムの実行時間は n*log(N) です。最小値と最大値 (O(n) で実行) log(N) 回を見つけます。
//Function call will be `find(0,N,k,in)`
//Retrieves the no.of smaller elements than first x(excluding) in union
public static int lowest(List<List<Integer>> in, int x){
int sum = 0;
for(List<Integer> lst: in){
if(x > lst.get(1))
sum += lst.get(1) - lst.get(0)+1;
else if((x >= lst.get(0) && x<lst.get(1)) || (x > lst.get(0) && x<=lst.get(1))){
sum += x - lst.get(0);
}
}
return sum;
}
//Retrieve the no.of smaller elements than last x(including) in union.
public static int highest(List<List<Integer>> in, int x){
int sum = 0;
for(List<Integer> lst: in){
if(x > lst.get(1))
sum += lst.get(1) - lst.get(0)+1;
else if((x >= lst.get(0) && x<lst.get(1)) || (x > lst.get(0) && x<=lst.get(1))){
sum += x - lst.get(0)+1;
}
}
return sum;
}
//Do binary search on the range.
public static int find(int low, int high, int k,List<List<Integer>> in){
if(low > high)
return -1;
int mid = low + (high-low)/2;
int lowIdx = lowest(in,mid);
int highIdx = highest(in,mid);
//k lies between the current numbers high and low indices
if(k > lowIdx && k <= highIdx) return mid;
//k less than lower index. go on to left side
if(k <= lowIdx) return find(low,mid-1,k,in);
// k greater than higher index go to right
if(k > highIdx) return find(mid+1,high,k,in);
else
return -1; // catch statement
}
リスト内のいくつの数値が、選択した数値 X よりも小さいかを数えることができます (すべての間隔を反復することにより)。ここで、この数が n より大きい場合、解は確実に X より小さくなります。同様に、この数が n 以下である場合、解は X 以上です。これらの観察に基づいて、二分探索を使用できます。 .
以下は Java の実装です。
public int nthElement( int[] lowerBound, int[] upperBound, int n )
{
int lo = Integer.MIN_VALUE, hi = Integer.MAX_VALUE;
while ( lo < hi ) {
int X = (int)( ((long)lo+hi+1)/2 );
long count = 0;
for ( int i=0; i<lowerBound.length; ++i ) {
if ( X >= lowerBound[i] && X <= upperBound[i] ) {
// part of interval i is less than X
count += (long)X - lowerBound[i];
}
if ( X >= lowerBound[i] && X > upperBound[i] ) {
// all numbers in interval i are less than X
count += (long)upperBound[i] - lowerBound[i] + 1;
}
}
if ( count <= n ) lo = X;
else hi = X-1;
}
return lo;
}