Leetcode 128 longest-consecutive-sequence最長連続シーケンスHash法および並列集合解法
文書ディレクトリ @[toc] タイトル要求 1. Hash法1(公式解法) 2. Hash法2(累積長さ) 3. Hash法3(双方向検索動的削除) 4. パラレルダイバーシチ法1(デュアルMapシミュレーションとダイバーシチを使用) 5. 並列調査法2(二重配列シミュレーションと調査セット、Mapは配列インデックスへの数値のマッピングを記録する) まとめ
自己実現のLeetCode関連問題解コードライブラリ:https://github.com/Yuri0314/Leetcode
テーマの要件
並べ替えられていない整数配列を指定し、最長連続シーケンスの長さを見つけます.
要求アルゴリズムの時間的複雑度はO(n)である.
例:
この問題を見て私の最初の考えは配列を先に並べ替えて、それから操作するのが簡単で、Hashを使う方法も考えましたが、どのように応用するか考えられませんでした.
問題解を見た後,Hashを適用した典型的なO(1)検索効率の問題であることが分かったが,Hash法と並列調査集を用いて実現した多様な実現方法をまとめ,順次説明する.
*注:暴力法と並べ替え法の実現と解釈は公式の問題解を参考にすることができる.https://leetcode.com/problems/longest-consecutive-sequence/solution/
1.Hash法1(公式解法)
公式解法はあまり説明しなくてもいいです.基本的なステップは:はすべての数字をSetに加えて重量を除去する. は、重量除去後のすべての数字について、次の操作を順次実行します. は、現在の配列が1つのシーケンス列のうちの最小値であるか否かを判断する(最小値でなければ、その列の最大長ではない計算される) .が最小値である場合、その値より1大きい数がセットsetにあるか否かを判定し続けるとともに、シーケンス列の長さ を統計する.レコードの最大シーケンス長値 を更新する.
2.Hash法2(累積長さ)
この方法の核心的な考え方は,遍歴した各数字に対して,その存在する列の長さを「その値より1小さい数レコードの列長」+「その値より1大きい数レコードの列長」+1とし,同時にデータ更新中に最大シーケンス列長値を更新することである.
この方法では、現在の数字より1または1より小さい数字に対応するレコードの列長をすばやく見つける必要があるため、Hashテーブルを用いて記録する.
3.Hash法3(双方向検索動的削除)
最初のHash法,すなわち公式に与えられたHash解法から,遍歴した現在の数字が存在するシーケンスの最小値であると判断する必要がないというステップが考えられる.実際には可能であり、公式の問題解でこの判断を行うのは、この数字が存在するシーケンス列の最小値でなければ、計算された存在するシーケンスの長さは必ず最小ではないからである.すなわち、他のシーケンスにわたる数字の計算された長さは、それよりも大きい可能性がある.重要なのは、同じシーケンスにある数字に対して、判断を加えなければ、繰り返し計算が発生する可能性があることです.
この問題に対して、各数値を巡回する際に、それぞれ大きく小さくする方法で、集合にその数値が存在するかどうかを検索し、計算長さを検索する過程でその数値を動的に削除し、1つのシーケンス列のすべての数値が1回しか計算されないようにすることができます.
4.並列調査法1(二重Mapシミュレーションを用いて調査する)
この問題では、配列内の数値を統計して連続シーケンスの列値の最大長を構成することができるため、このような列値は明らかに1つの集合であり、絶えず集計して検索することで対応する集合に数値を加えることができます.明らかに、これはセットを使用して解決することができます.
UnionFindでは、2つのMapを定義し、その数値から集合ツリーのルートへのマッピングと、その数値から集合ストレージ要素の数へのマッピングを表します.maxCount変数を使用して、要素が対応する集合に連続的に組み込まれる過程での最大長さを記録します.
使用する場合は、入力配列の各数値を巡り、unionメソッドを呼び出して現在の数値とその値より1大きい数値を集計します.
注意:テーマ要求のO(n)時間の複雑さを達成するためには,要素が存在する集合のルート要素を検索する過程で経路圧縮操作を行う必要がある.
5.並列調査法2(二重配列シミュレーションと調査セット、Mapは配列インデックスへの数値のマッピングを記録する)
前の並列集合法と同様に,この方法におけるUnionFind並列集合クラスは2つの配列を用いて実現され,それぞれデジタル対応集合ツリールートインデックスとデジタル対応集合格納要素数を表し,デジタル値から対応インデックス位置へのマッピングは1つのMapを用いて記録される点で基本構想は一致している.
注意:このような実装では、各遍歴した数字を双方向からunion試行しなければならない.すなわち、unionは現在の数字より1と1より大きい数である.そうでなければ、unionの大きい1の数だけを試してみると、配列の要素が[1,2,3,4]のように、ある列の大きな数が小数の前に現れると、誤った答えが得られます.
まとめ
上記のすべての方法の均等時間複雑度はO(n),空間複雑度はO(n)であった.
自己実現のLeetCode関連問題解コードライブラリ:https://github.com/Yuri0314/Leetcode
テーマの要件
並べ替えられていない整数配列を指定し、最長連続シーケンスの長さを見つけます.
要求アルゴリズムの時間的複雑度はO(n)である.
例:
: [100, 4, 200, 1, 3, 2]
: 4
: [1, 2, 3, 4]。 4。
この問題を見て私の最初の考えは配列を先に並べ替えて、それから操作するのが簡単で、Hashを使う方法も考えましたが、どのように応用するか考えられませんでした.
問題解を見た後,Hashを適用した典型的なO(1)検索効率の問題であることが分かったが,Hash法と並列調査集を用いて実現した多様な実現方法をまとめ,順次説明する.
*注:暴力法と並べ替え法の実現と解釈は公式の問題解を参考にすることができる.https://leetcode.com/problems/longest-consecutive-sequence/solution/
1.Hash法1(公式解法)
公式解法はあまり説明しなくてもいいです.基本的なステップは:
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums)
num_set.add(num);
int longestStrak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int curNum = num;
int curStrak = 1;
while (num_set.contains(++curNum)) ++curStrak;
longestStrak = Math.max(longestStrak, curStrak);
}
}
return longestStrak;
}
}
2.Hash法2(累積長さ)
この方法の核心的な考え方は,遍歴した各数字に対して,その存在する列の長さを「その値より1小さい数レコードの列長」+「その値より1大きい数レコードの列長」+1とし,同時にデータ更新中に最大シーケンス列長値を更新することである.
この方法では、現在の数字より1または1より小さい数字に対応するレコードの列長をすばやく見つける必要があるため、Hashテーブルを用いて記録する.
class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int ans = 0;
for (int num : nums) {
if (!map.containsKey(num)) {
int leftLength = (map.containsKey(num - 1)) ? map.get(num - 1) : 0;
int rightLength = (map.containsKey(num + 1)) ? map.get(num + 1) : 0;
int curLength = leftLength + rightLength + 1;
map.put(num - leftLength, curLength);
map.put(num + rightLength, curLength);
map.put(num, curLength);
ans = Math.max(ans, curLength);
}
}
return ans;
}
}
3.Hash法3(双方向検索動的削除)
最初のHash法,すなわち公式に与えられたHash解法から,遍歴した現在の数字が存在するシーケンスの最小値であると判断する必要がないというステップが考えられる.実際には可能であり、公式の問題解でこの判断を行うのは、この数字が存在するシーケンス列の最小値でなければ、計算された存在するシーケンスの長さは必ず最小ではないからである.すなわち、他のシーケンスにわたる数字の計算された長さは、それよりも大きい可能性がある.重要なのは、同じシーケンスにある数字に対して、判断を加えなければ、繰り返し計算が発生する可能性があることです.
この問題に対して、各数値を巡回する際に、それぞれ大きく小さくする方法で、集合にその数値が存在するかどうかを検索し、計算長さを検索する過程でその数値を動的に削除し、1つのシーケンス列のすべての数値が1回しか計算されないようにすることができます.
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int ans = 0;
for (int num : nums) set.add(num);
for (int num : nums) {
int length = 1;
int cur = num;
while (set.contains(--cur)) {
++length;
set.remove(cur);
}
cur = num;
while (set.contains(++cur)) {
++length;
set.remove(cur);
}
set.remove(num);
ans = Math.max(ans, length);
}
return ans;
}
}
4.並列調査法1(二重Mapシミュレーションを用いて調査する)
この問題では、配列内の数値を統計して連続シーケンスの列値の最大長を構成することができるため、このような列値は明らかに1つの集合であり、絶えず集計して検索することで対応する集合に数値を加えることができます.明らかに、これはセットを使用して解決することができます.
UnionFindでは、2つのMapを定義し、その数値から集合ツリーのルートへのマッピングと、その数値から集合ストレージ要素の数へのマッピングを表します.maxCount変数を使用して、要素が対応する集合に連続的に組み込まれる過程での最大長さを記録します.
使用する場合は、入力配列の各数値を巡り、unionメソッドを呼び出して現在の数値とその値より1大きい数値を集計します.
注意:テーマ要求のO(n)時間の複雑さを達成するためには,要素が存在する集合のルート要素を検索する過程で経路圧縮操作を行う必要がある.
class Solution {
public int longestConsecutive(int[] nums) {
UnionFind uf = new UnionFind(nums);
for (int num : nums) {
uf.union(num, num + 1);
}
return uf.getMaxCount();
}
class UnionFind {
private Map<Integer, Integer> unionSet = new HashMap<Integer, Integer>();
private Map<Integer, Integer> countSet = new HashMap<Integer, Integer>();
private int maxCount;
public UnionFind(int[] nums) {
for (int num : nums) {
unionSet.put(num, num);
countSet.put(num, 1);
}
maxCount = nums.length > 0 ? 1 : 0;
}
public int getRoot(int num) {
if (num == unionSet.get(num))
return num;
else {
unionSet.put(num, getRoot(unionSet.get(num)));
return unionSet.get(num);
}
}
public void union(int a, int b) {
if (!unionSet.containsKey(a) || !unionSet.containsKey(b)) return;
int rootA = getRoot(a);
int rootB = getRoot(b);
if (rootA == rootB) return;
int newCount = countSet.get(rootA) + countSet.get(rootB);
if (countSet.get(rootA) < countSet.get(rootB)) {
unionSet.put(rootA, rootB);
countSet.put(rootB, newCount);
}
else {
unionSet.put(rootB, rootA);
countSet.put(rootA, newCount);
}
maxCount = Math.max(maxCount, newCount);
}
public int getMaxCount() {
return this.maxCount;
}
}
}
5.並列調査法2(二重配列シミュレーションと調査セット、Mapは配列インデックスへの数値のマッピングを記録する)
前の並列集合法と同様に,この方法におけるUnionFind並列集合クラスは2つの配列を用いて実現され,それぞれデジタル対応集合ツリールートインデックスとデジタル対応集合格納要素数を表し,デジタル値から対応インデックス位置へのマッピングは1つのMapを用いて記録される点で基本構想は一致している.
注意:このような実装では、各遍歴した数字を双方向からunion試行しなければならない.すなわち、unionは現在の数字より1と1より大きい数である.そうでなければ、unionの大きい1の数だけを試してみると、配列の要素が[1,2,3,4]のように、ある列の大きな数が小数の前に現れると、誤った答えが得られます.
class Solution {
public int longestConsecutive(int[] nums) {
UnionFind uf = new UnionFind(nums.length);
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (map.containsKey(nums[i])) continue;
map.put(nums[i], i);
if (map.containsKey(nums[i] + 1))
uf.union(i, map.get(nums[i] + 1));
if (map.containsKey(nums[i] - 1))
uf.union(i, map.get(nums[i] - 1));
}
return uf.getMaxCount();
}
class UnionFind {
private int[] unionSet;
private int[] countSet;
private int maxCount;
public UnionFind(int length) {
unionSet = new int[length];
countSet = new int[length];
for (int i = 0; i < length; ++i) {
unionSet[i] = i;
countSet[i] = 1;
}
maxCount = length > 0 ? 1 : 0;
}
public int getRoot(int i) {
while (i != unionSet[i]) {
unionSet[i] = unionSet[unionSet[i]];
i = unionSet[i];
}
return i;
}
public void union(int a, int b) {
int rootA = getRoot(a);
int rootB = getRoot(b);
if (rootA == rootB) return;
if (countSet[rootA] < countSet[rootB]) {
unionSet[rootA] = unionSet[rootB];
countSet[rootB] += countSet[rootA];
maxCount = Math.max(maxCount, countSet[rootB]);
}
else {
unionSet[rootB] = unionSet[rootA];
countSet[rootA] += countSet[rootB];
maxCount = Math.max(maxCount, countSet[rootA]);
}
}
public int getMaxCount() {
return this.maxCount;
}
}
}
まとめ
上記のすべての方法の均等時間複雑度はO(n),空間複雑度はO(n)であった.