對“求數組中所有和為某固定數的所有數對”的算法的簡單思考

2019-11-17 03:52:00

字體：大中小

來源：轉載

供稿：網友

一、題目描述

    有一個數組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;
        }

上一篇：個人管理－個人知識管理

下一篇：分享WordPress博客搜索引擎優化的六點經驗