1. トピックの説明
1000 個の整数を格納する配列 a[1000] があります。配列内で合計が M となる数値のペアをすべて見つけてください。たとえば、配列が -1,2,4,6,5,3,4,2,9,0,8,3 の場合、合計が 8 となる数値のペアは (-1,9), (2, 6)、( 4,4)、(5,3)、(5,3)、(0,8)。
2. 最も一般的なアルゴリズム
単純化できない複雑さの場合、この問題に対する最も単純なアルゴリズムは次のとおりです。
private static List<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> 結果 = new List<int[]>();
for (int i = 0; i < arr.Length; i++)
{
int ExpectNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] == ExpectNum)
{
result.Add(new int[]{arr[i], ExpectNum});
}
}
}
結果を返します。
}
2 レベルのループを使用して、合計が固定数 sumTotal であるすべてのペアを検索し、見つかったペアを List に保存します。ただし、このアルゴリズムの複雑さは少し高く、実際にはトラバーサル中にいくつかの反復作業を実行します。
1) 後続のループで以前にペアになったシーケンスを処理する必要はありません。
2) 和がsumTotalとなる数値を検索する場合、相互に利用できる処理がいくつかあるはずです。
これら 2 つの点に基づいて、01 のナップザックまたは動的プログラミングのアイデア (おそらく不適切かもしれませんが、私はこれら 2 つのアイデアを表面的に理解しています) を引用して、このアルゴリズムを改善し、再帰を使用して動作させることができます。
2. 再帰的アルゴリズムを使用する
再帰アルゴリズムを使用したコードは次のとおりです。
private static List<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> 結果 = new List<int[]>();
int[] nextArr = 新しい int[長さ];
int nextLength = 0;
int ExpectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < 長さ; i++)
{
if (arr[i] == ExpectNum)
{
int CircleCount = arr[0] == ExpectNum ? findEndNumCount : findStartNumCount;
サークル数 += 1;
for (int j = 0; j < CircleCount; j++)
{
result.Add(new int[] { arr[0], ExpectNum });
}
findEndNumCount++;
}
else if (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] { ExpectNum, arr[0] });
}
findStartNumCount++;
}
それ以外
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (nextResult の int[] 項目)
{
result.Add(項目);
}
}
結果を返します。
}
各再帰の後、一致がチェックされていないすべての数値が次の再帰で処理するために新しい配列に形成されますが、これは大量のスペースを無駄にし、特に配列が大きい場合は大量のメモリを消費します。 。毎回新しい配列を再帰的に作成しないようにするには、元の配列で配列を処理し、一致する数値を配列から削除し、後続の数値を前方に移動して置き換えます。
3. 配列動的変更アルゴリズム
このアルゴリズムのコードは次のとおりです。
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> 結果 = new List<int[]>();
int startIndex = 0、endIndex = arr.Length - 1;
while (startIndex < endIndex)
{
int ExpectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
if (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
if (arr[i] == ExpectNum)
{
int CircleCount = arr[startIndex] == ExpectNum ? findEndNumCount : findStartNumCount;
サークル数 += 1;
for (int iStart = 0; iStart < CircleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
終了インデックス--;
私 - ;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] { ExpectNum, arr[i] });
}
findStartNumCount++;
終了インデックス--;
私 - ;
}
}
startIndex++;
}
結果を返します。
}
このアルゴリズムは元の配列のデータを破壊します。
4. 3つのアルゴリズムの時間の比較
後の 2 つのアルゴリズムの本来の目的は時間の複雑さを軽減することですが、特定のテストでは最初のアルゴリズムよりもそれほど優れているわけではありません。特に、再帰的アルゴリズムは最初のアルゴリズムよりも大幅に時間がかかります。もしかしたら、私のアイデアに根本的な問題があるのかもしれません。あるいは、この例が単純すぎて、モバイル データが占有する時間が明らかになってしまうのかもしれません。
私はアルゴリズムについてあまり研究したことがありませんが、より完璧な解決策があるはずだと専門家がアドバイスしてくれることを願っています。
5. すべてのコード
static void Main(string[] args)
{
const int NUM_COUNT = 8000;
const int MIN_NUM = -4;
const int MAX_NUM = 12;
const int TOTAL = 8;
int[] arr = GenerateArray(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("生成される数値は次のとおりです:n-------------------------------------------- ---- -");
//PrintNumArray(arr);
//通常の方法
TimeSpannormalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
ストップウォッチnormalStw = new Stopwatch();
NormalStw.Start();
List<int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);
double NormalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
NormalStw.Stop();
doublenormalRealTime =normalStw.Elapsed.TotalMilli秒;
// 通常の結果を出力します
//Console.WriteLine("通常の方法を使用した結果の数値ペアは次のとおりです:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
// 再帰の方法
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
ストップウォッチ recuStw = new Stopwatch();
recuStw.Start();
List<int[]> resultUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);
double recuCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMilliseconds;
recuStw.Stop();
double recuRealTime = recuStw.Elapsed.TotalMilli秒;
// 再帰結果を出力する
//Console.WriteLine("再帰法を使用した結果の数値ペアは次のとおりです:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// 高度な方法
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
ストップウォッチ advStw = new Stopwatch();
advStw.Start();
List<int[]> resultUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
double advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliseconds;
advStw.Stop();
double advRealTime = advStw.Elapsed.Totalミリ秒;
// 詳細な結果を印刷する
//Console.WriteLine("高度な方法を使用した結果の数値ペアは次のとおりです:n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n===============================n使用時間:n---- ----------------------------------");
Console.WriteLine(String.Format("Normal : count - {0} Cpu Time - {1} Real Time - {2}", resultUseNormalWay.Count,normalCupTime,normalRealTime));
Console.WriteLine(String.Format("再帰: カウント - {0} Cpu 時間 - {1} リアルタイム - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("Advanced : count - {0} Cpu Time - {1} Real Time - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Console.Read();
}
private static int[] GenerateArray(int numCount, int minValue, int maxValue)
{
int[] arr = 新しい int[numCount];
ランダム rdm = new Random((int)DateTime.Now.Ticks);
for (int i = 0; i < arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
arrを返します。
}
プライベート静的 void PrintNumArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
if (i > 0 && i % 20 == 0)
{
Console.Write("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Console.Write("n");
}
private static void PrintNumPairs(List<int[]> numList)
{
for (int i = 0; i < numList.Count; i++)
{
if (i > 0 && i % 10 == 0)
{
Console.Write("n");
}
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
}
Console.Write("n");
}
private static List<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> 結果 = new List<int[]>();
for (int i = 0; i < arr.Length; i++)
{
int ExpectNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] == ExpectNum)
{
result.Add(new int[]{arr[i], ExpectNum});
}
}
}
結果を返します。
}
private static List<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> 結果 = new List<int[]>();
int[] nextArr = 新しい int[長さ];
int nextLength = 0;
int ExpectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < 長さ; i++)
{
if (arr[i] == ExpectNum)
{
int CircleCount = arr[0] == ExpectNum ? findEndNumCount : findStartNumCount;
サークル数 += 1;
for (int j = 0; j < CircleCount; j++)
{
result.Add(new int[] { arr[0], ExpectNum });
}
findEndNumCount++;
}
else if (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] { ExpectNum, arr[0] });
}
findStartNumCount++;
}
それ以外
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (nextResult の int[] 項目)
{
result.Add(項目);
}
}
結果を返します。
}
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> 結果 = new List<int[]>();
int startIndex = 0、endIndex = arr.Length - 1;
while (startIndex < endIndex)
{
int ExpectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
if (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
if (arr[i] == ExpectNum)
{
int CircleCount = arr[startIndex] == ExpectNum ? findEndNumCount : findStartNumCount;
サークル数 += 1;
for (int iStart = 0; iStart < CircleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
終了インデックス--;
私 - ;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] { ExpectNum, arr[i] });
}
findStartNumCount++;
終了インデックス--;
私 - ;
}
}
startIndex++;
}
結果を返します。
}
-