1 つのアイデア: まあ、とにかくリストをソートする必要があると思いますが、マージやクイックソートはできません。しかし、メモリがあれば、整数の並べ替えをカウントすることからアイデアを使用できます。
したがって、0 から最大の int 値までの 0 と 1 の配列を作成し、値がある場合はそれを 1 で埋めてから、最大連続配列を見つけることができます。
2 アイデア: 値の辞書を作成し、最小値と最大値を見つけます - すべての O(N) 操作:
dict = {1: 1, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 10: 10}
min = 1
max = 10
次に、同様に行っi in range(min, max)て、最長の連続サブセットを見つけます
>>> d = [1, 3, 5, 7, 4, 6, 10]
>>> s = set(d)
>>> mind = min(d)
>>> maxd = max(d)
>>> a, b, j = 0, 0, 0
>>> for i in range(mind, maxd):
if i not in s:
if (b - a) < (i - j - 1):
a, b = j, i - 1
j = i + 1
>>> a, b
(3, 7)
しかし、これは次のような疎なリストでは遅くなる可能性があります[1, 9000, 100000]
EDIT : Grigor Gevorgyanの非常に優れた回答に基づいて、Python での O(N) 辞書ソリューションのコードを次に示します (シンプルさが大好きです!!!)
l = [1, 3, 5, 7, 4, 6, 10]
d = {x:None for x in l}
print d
for (k, v) in d.iteritems():
if v is not None: continue
a, b = d.get(k - 1), d.get(k + 1)
if a is not None and b is not None: d[k], d[a], d[b] = k, b, a
elif a is not None: d[a], d[k] = k, a
elif b is not None: d[b], d[k] = k, b
else: d[k] = k
print d
m = max(d, key=lambda x: d[x] - x)
print m, d[m]
出力：
{1: None, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 3, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 4, 4: 3, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 5, 4: 3, 5: 3, 6: None, 7: None, 10: None}
{1: 1, 3: 6, 4: 3, 5: 3, 6: 3, 7: None, 10: None}
{1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: None}
{1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: 10}
3 7
を使用して非常に簡単なソリューションを作成しましたHashSet。containsとは O(1) 操作であるためremove、ランダムなセット項目から新しい間隔を作成し、完全なサイズを発見するまで間隔を「拡張」し、進むにつれてセットから項目を削除することができます。これは、間隔を「繰り返す」ことを防ぐものであるため、削除が重要です。
このように考えると役立つかもしれません。リストには K 個の間隔があり、そのサイズを合計すると N になります。あなたの仕事は、間隔やアイテムを繰り返さずに、これらの間隔が何であるかを発見することです。これが、HashSet がこの仕事に最適な理由です。間隔を広げると、セットからアイテムを効率的に削除できます。あとは、最大の間隔を追跡するだけです。
HashSeti = interval.start-1i削除し、 と の両方をiデクリメントします。iinterval.startinterval.end) 。Javaでの解決策は次のとおりです。
public class BiggestInterval {
static class Interval {
int start;
int end;
public Interval(int base) {
this(base,base);
}
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public int size() {
return 1 + end - start;
}
@Override
public String toString() {
return "[" + start + "," + end + "]";
}
}
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(biggestInterval(Arrays.asList(1,3,5,7,4,6,10)));
}
public static Interval biggestInterval(List<Integer> list) {
HashSet<Integer> set = new HashSet<Integer>(list);
Interval largest = null;
while(set.size() > 0) {
Integer item = set.iterator().next();
set.remove(item);
Interval interval = new Interval(item);
while(set.remove(interval.start-1)) {
interval.start--;
}
while(set.remove(interval.end+1)) {
interval.end++;
}
if (largest == null || interval.size() > largest.size()) {
largest = interval;
}
}
return largest;
}
}
平均的な O(1) ハッシュ テーブルで構築された辞書を考えると、これは直線的です。
L = [1,3,5,7,4,6,10]
a_to_b = {}
b_to_a = {}
for i in L:
if i+1 in a_to_b and i-1 in b_to_a:
new_a = b_to_a[i-1]
new_b = a_to_b[i+1]
a_to_b[new_a] = new_b
b_to_a[new_b] = new_a
continue
if i+1 in a_to_b:
a_to_b[i] = a_to_b[i+1]
b_to_a[a_to_b[i]] = i
if i-1 in b_to_a:
b_to_a[i] = b_to_a[i-1]
a_to_b[b_to_a[i]] = i
if not (i+1 in a_to_b or i-1 in b_to_a):
a_to_b[i] = i
b_to_a[i] = i
max_a_b = max_a = max_b = 0
for a,b in a_to_b.iteritems():
if b-a > max_a_b:
max_a = a
max_b = b
max_a_b = b-a
print max_a, max_b
これは、グリゴールに似たソリューションです。2 つの主な違いは、このソリューションが他のインデックスではなくシーケンシャル セットの長さを格納することと、これにより最後のハッシュ セットの繰り返しが不要になることです。
配列を反復処理する
隣接するセット エンドポイントを探して更新することにより、ハッシュマップを作成します。
キー- 配列値
値- キーがシーケンシャル セットのエンドポイントである場合、そのセットの長さを格納します。それ以外の場合は、真実を保ち、物事を一度だけ検討してください。
現在のセット サイズが最長の場合、最長セット サイズと最長セット開始を更新します。
わかりやすくするための JavaScript の実装と、実際の動作を確認するため のフィドルを次に示します。
var array = [1,3,5,7,4,6,10];
//Make a hash of the numbers - O(n) assuming O(1) insertion
var longestSetStart;
var longestSetSize = 0;
var objArray = {};
for(var i = 0; i < array.length; i++){
var num = array[i];
if(!objArray[num]){//Only consider numbers once
objArray[num] = 1;//Initialize to 1 item in the set by default
//Get the updated start and end of the current set
var currentSetStart = num;//Starting index of the current set
var currentSetEnd = num;//Ending index of the current set
//Get the updated start of the set
var leftSetSize = objArray[num - 1];
if(leftSetSize){
currentSetStart = num - leftSetSize;
}
//Get the updated end of the set
var rightSetSize = objArray[num + 1];
if(rightSetSize){
currentSetEnd = num + rightSetSize;
}
//Update the endpoints
var currentSetSize = currentSetEnd - currentSetStart + 1;
objArray[currentSetStart] = currentSetSize;
objArray[currentSetEnd] = currentSetSize;
//Update if longest set
if(currentSetSize > longestSetSize){
longestSetSize = currentSetSize;
longestSetStart = currentSetStart;
}
}
}
var longestSetEnd = longestSetStart + longestSetSize - 1;
秘訣は、項目をリストではなくセットとして考えることです。これにより、アイテム-1またはアイテム+1が存在するかどうかをセットで確認できるため、連続する範囲の開始または終了にあるアイテムを識別できます。これにより、線形の時間と空間で問題を解決できます。
擬似コード:
C# コード:
static Tuple<int, int> FindLargestContiguousRange(this IEnumerable<int> items) {
var itemSet = new HashSet<int>(items);
// find contiguous ranges by identifying their starts and scanning for ends
var ranges = from item in itemSet
// is the item at the start of a contiguous range?
where !itemSet.Contains(item-1)
// find the end by scanning upward as long as we stay in the set
let end = Enumerable.Range(item, itemSet.Count)
.TakeWhile(itemSet.Contains)
.Last()
// represent the contiguous range as a tuple
select Tuple.Create(item, end);
// return the widest contiguous range that was found
return ranges.MaxBy(e => e.Item2 - e.Item1);
}
注: MaxBy は MoreLinq からのものです
テスト
小さな健全性チェック:
new[] {3,6,4,1,8,5}.FindLargestContiguousRange().Dump();
// prints (3, 6)
大きな連続したリスト:
var zeroToTenMillion = Enumerable.Range(0, (int)Math.Pow(10, 7)+1);
zeroToTenMillion.FindLargestContiguousRange().Dump();
// prints (0, 10000000) after ~1 seconds
大きな断片化されたリスト:
var tenMillionEvens = Enumerable.Range(0, (int)Math.Pow(10, 7)).Select(e => e*2);
var evensWithAFewOdds = tenMillionEvens.Concat(new[] {501, 503, 505});
evensWithAFewOdds.FindLargestContiguousRange().Dump();
// prints (500, 506) after ~3 seconds
複雑
このアルゴリズムは O(N) 時間と O(N) 空間を必要とします。ここで、N はリスト内のアイテムの数であり、集合操作が一定時間であると仮定します。
セットがアルゴリズムによって構築されるのではなく、入力として与えられた場合、必要なのは O(1) スペースだけであることに注意してください。
（一部のコメントは、これは二次時間であると言っています。範囲の開始点にあるアイテムだけでなく、すべてのアイテムがスキャンをトリガーしたと仮定したと思います。アルゴリズムがそのように機能した場合、それは実際に二次時間になります。）
免責事項: ソリューションはハッシュテーブルに基づいているため、実行時間は想定されたものであり、最悪の場合ではありません。
この O(n) ソリューションは、整数が一意であることに依存します。それらが一意でない場合は、O(1) 挿入とメンバーシップ ルックアップを使用してハッシュセットを作成し、リストを調べて、既に見つかった番号をスキップします。
値が範囲の始まりであり、キーがそれらの範囲の終わりに収まる数字である O(1) ルックアップ/挿入ハッシュマップを作成します。値 v とキー k の場合、これは v から始まり k-1 で終わる範囲がキー k にあることを意味します。
番号のリストを調べます。数値 n ごとに、マップのキー n に値 v があるかどうかを確認します。これは、最後に n を許可する v から始まる範囲があることに対応します。存在する場合は、v をキー n+1 に移動し、キー n のエントリを削除します。範囲がない場合は、キー n+1 に n を挿入します。
数値は一意であるため、最終的に範囲が重複することはありませんが、連続した範囲が存在する可能性があります。マップのキーと値のペアを実行します。各キー k と値 v について、マップがキー k1 = v で値 v1 を持っている場合、v1 から k-1 までの範囲があることを意味します。v1 を k に挿入し、エントリ k1/v1 を削除します。
移動最大値を使用して、マップの k/v エントリを調べて、サイズ kv の最大範囲 [v,k-1] を見つけます。
あなたの例：
setup:
l = [1,3,5,7,4,6,10]
m = {}
iteration:
process 1 : m = {2->1}
process 3 : m = {2->1, 4->3}
process 5 : m = {2->1, 4->3, 6->5}
process 7 : m = {2->1, 4->3, 6->5, 8->7}
process 4 : m = {2->1, 5->3, 6->5, 8->7}
process 6 : m = {2->1, 5->3, 7->5, 8->7}
process 10 : m = {2->1, 5->3, 7->5, 8->7, 11->10}
concatenation of contiguous ranges:
initial: m = {2->1, 5->3, 7->5, 8->7, 11->10}
first concatenation: m = {2->1, 7->3, 8->7, 11->10}, k=7, v=5, k1=5, v1=3
second concatenation: m = {2->1, 8->3, 11->10}, k=8, v=7, k1=7, v1=3
result:
largest range : [3,7] of size 5