1. Topic description
There is an array a[1000], which stores 1000 integers. Please find all pairs of numbers in the array whose sum is M. For example, the array is -1,2,4,6,5,3,4,2,9,0,8,3, then the number pairs whose sum is 8 are (-1,9), (2,6), ( 4,4), (5,3), (5,3), (0,8).
2. The most common algorithm
In the case of irreducible complexity, the simplest algorithm for this problem is as follows:
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;
}
Use a two-level loop to find all pairs whose sum is a fixed number sumTotal, and store the found pairs in a List. However, the complexity of this algorithm is a bit high, and it actually does some repetitive work during traversal:
1) There is no need to process the previously paired sequence in subsequent loops.
2) When searching for a number whose sum is sumTotal, there should be some processes that can be used mutually.
Based on these two points, you can quote some 01 knapsack or dynamic programming ideas (perhaps inappropriately, I have a superficial understanding of these two ideas) to improve this algorithm and use recursion to operate.
2. Use recursive algorithm
The code using the recursive algorithm is as follows:
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;
}
After each recursion, all the numbers that have not been checked for matching are formed into a new array for processing in the next recursion, but this wastes a huge amount of space, especially when the array is large, it will consume a lot of memory. In order not to create a new array recursively every time, you can process it on the original array, remove the matching numbers from the array, and move the subsequent numbers forward to replace them.
3. Array dynamic change algorithm
The code for this algorithm is as follows:
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;
}
This algorithm will destroy the data of the original array.
4. Comparison of the time of three algorithms
Although the original intention of the latter two algorithms is to reduce time complexity, they are not much better than the first algorithm in specific tests. In particular, the recursive algorithm takes significantly longer than the first algorithm. Maybe there is a fundamental problem with my idea, or maybe this example is too simple and makes the time occupied by mobile data obvious.
I have never done much research on algorithms. I hope experts can give me some advice. I believe there must be a more perfect solution.
5. All codes
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;
}
-