一、題目描述
有一個數組a[1000]，裡面存放了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)。
二、最普通的演算法
在不可率複雜度的情況下，對於這個問題的最簡單的演算法如下：
private static List<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> result = 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});
}
}
}
return result;
}
利用兩層循環找出所有和為固定數sumTotal的所有數對，將找到的數對存入List中。但是這個演算法複雜度有點高，實際上在遍歷的時候做了一些重複的工作：
1) 後續循環的時候沒有必要對前面已經配對的數列進行處理。
2）找出與某個數字和為sumTotal的數時，應該可以有一些可以互相利用的過程。
基於這兩點，可以引用一些01背包或動態規劃的想法（或許引用得不恰當，我對這兩種想法和理解很膚淺）來對這個演算法進行改進，利用遞歸來操作。
二、採用遞迴演算法
採用遞歸演算法的程式碼如下：
private static List<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> result = new List<int[]>();
int[] nextArr = new int[length];
int nextLength = 0;
int expectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < length; i++)
{
if (arr[i] == expectNum)
{
int circleCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
circleCount += 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++;
}
else
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] item in nextResult)
{
result.Add(item);
}
}
return result;
}
每遞歸一次後，將所有沒有檢查過匹配的數字再組成一個新的數組以便在下一次遞歸中來處理，但這麼做浪費了巨大的空間，特別是數組很大的情況下會消耗很多內存。為了不每次遞歸創建新的數組，可以在原來的數組上處理，將已經匹配的數字從數組中剔出，將後續數字前移替補。
三、數組動態改變演算法
這種演算法的程式碼如下：
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> result = 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;
circleCount += 1;
for (int iStart = 0; iStart < circleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
i--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] { expectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
i--;
}
}
startIndex++;
}
return result;
}
這種演算法會破壞原有數組的資料的。
四、三種演算法時間的比較
雖然後兩種演算法的初衷是為了減少時間複雜度，但在具體測試中並沒有比第一種演算法優越多少，特別是遞歸的演算法比第一種演算法所花費的時間還明顯加長。或許我的想法從基礎上就有問題，也或許是這個例子過於簡單使得行動數據佔用的時間明顯凸現出來了。
一直未對演算法有太多研究，希望高手們能指點一二，我相信有肯定有更完美的解決方案。
五、所有碼
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("The numbers generated are:n------------------------------------ -");
//PrintNumArray(arr);
// Normal way
TimeSpan normalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Stopwatch normalStw = new Stopwatch();
normalStw.Start();
List<int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);
double normalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
normalStw.Stop();
double normalRealTime = normalStw.Elapsed.TotalMilliseconds;
// Print Normal Result
//Console.WriteLine("The result number pairs using normal way are:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
// Recursion way
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Stopwatch 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.TotalMilliseconds;
// Print Recursion Result
//Console.WriteLine("The result number pairs using recusion way are:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// Advanced way
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
Stopwatch 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.TotalMilliseconds;
// Print Advanced Result
//Console.WriteLine("The result number pairs using advanced way are:n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n================================nThe time used:n---- -------------------------------");
Console.WriteLine(String.Format("Normal : count - {0} Cpu Time - {1} Real Time - {2}", resultUseNormalWay.Count, normalCupTime, normalRealTime));
Console.WriteLine(String.Format("Recursion: count - {0} Cpu Time - {1} Real Time - {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 = new int[numCount];
Random rdm = new Random((int)DateTime.Now.Ticks);
for (int i = 0; i < arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
return arr;
}
private static 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[]> result = 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});
}
}
}
return result;
}
private static List<int[]> UseRecursion(int[] arr, int length, int sumTotal)
{
List<int[]> result = new List<int[]>();
int[] nextArr = new int[length];
int nextLength = 0;
int expectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < length; i++)
{
if (arr[i] == expectNum)
{
int circleCount = arr[0] == expectNum ? findEndNumCount : findStartNumCount;
circleCount += 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++;
}
else
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] item in nextResult)
{
result.Add(item);
}
}
return result;
}
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> result = 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;
circleCount += 1;
for (int iStart = 0; iStart < circleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
i--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != expectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] { expectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
i--;
}
}
startIndex++;
}
return result;
}
-