给你一个整型数组，我想找出来最大的两个数，能帮我写一个算法吗？

---

在上一遍我们已经解读过这道题目了，包括我们能想到的问题。这里我们按照解决算法题的一般步骤再来一起分析一下这道题：

1. 确保我们理解了问题，并且尝试一个例子，确认理解无误。

那现在我们澄清一下问题，我们需要从这样的数组中{ 4， 5，2，3，1}中找出最大的两个数字返回{4，5}，当数组为空的时候我们也返回空的数组。

2. 想想你可以用什么方法解决问题，你会选择哪一种，为什么？

我们不想先对他进行排序，原因有两个，数组是引用类型，排序会改变原来的数据结果，我相信你调用别人SDK的时候，肯定也不想自己的数据莫名其妙的被改变了对吧，即使我们能保证不改变原来的次序，我们也会引入额外的存储空间，另外，题目当中没有要求将所有的数字排序返回，排序似乎有些浪费。而且，一般的排序最好能做到n log(n), 而这道题其实只需要o(n)就能解决。

3. 解释你的算法和实现的方法

解释我们的算法，我们申明两个临时变量， max， secondmax，然后开始扫描数组。若数组中当前的数字比max还大，我们就替换到max，当然替换之前，先将max赋值到secondmax里去，若数组中当前的数字比max小，我们再比较是否比secondmax大，倘若大，我们将直接将其赋值到secondmax上去，其他情况我们就不用处理啦。

4. 写代码的时候，记住，一定要解释你现在在干什么

public static int[] FindMaxTwo(int[] array)         {             // 如果输入的数组是空，或者数组的长度只有一个，我们也就没有必要处理了，直接返回             if (array == null || array.Length == 1) return array;             // 定义两个临时变量，想一想我们为什么要赋值为int.minvalue             int max = int.MinValue;             int secondMax = int.MinValue;             // 开始扫描数组             for (int index = 0; index < array.Length; index++)             {                 // 如果当前的数字比max还大，我们将改变secondmax的值，然后该表max                 if (array[index] >= max)                 {                     secondMax = max;                     max = array[index];                 }                 // 如果当前数字没有比max大，但是比secondmax大，我们直接改变secondmax的值                 else if (array[index] >= secondMax)                 {                     secondMax = array[index];                 }             }             // 好了，我们将得到的这两个值放到数组里，准备返回吧             int[] result = new int[2];             result[0] = secondMax;             result[1] = max;             return result;         }

5. 拿一个实例，Work Through你的代码（省略了哈)

6. 修复缺陷，保证异常情况都被考虑到。我们需要列出来这里的一些

特殊情况，如数组中如果存在相同的数字而且都是最大的数，我们返回什么呢？如{5，3，4，1，5}，返回{4，5}还是{5，5}呢，不一样的要求会对处理的细节有所差别。如果数组中全是负数我们的代码还能返回期待的结果吗？

尝试一下： 大家可以把intmax= int.MinValue; int secondMax = int.MinValue;改成intmax;int secondmax;再试试 {-5，-2，-4，-3，-1}试试看，这里会出现一个bug。其根本原因在于，int 的默认值是0。

再尝试一下：我们先定义了两个临时变量，之后又申明了一个数组，是不是有点浪费。不简洁有没有？好的，我们给它优化一下：

public static int[] FindMaxTwoImproved2(int[] array)         {             if (array == null || array.Length == 1) return array;             // Here is a bug when the max value is negative since the initial value in the int array is 0             int[] result = new int[2];             // This is to fix the bug above             for (var index = 0; index < result.Length; index++)             {                 result[index] = int.MinValue;             }             Console.WriteLine(result[1]);             for (int index = 0; index < array.Length; index++)             {                 if (array[index] >= result[0])                 {                     result[0] = result[1];                     result[1] = array[index];                 }                 else if (array[index] >= result[1])                 {                     result[0] = array[index];                 }             }             return result;         }

回到上一篇的问题中来，我们曾今问过K是否会变，能不能做到以不变应万变，动态一些，你让我们返回几个我们就返回几个呢？当然可以，这次我们申明一个长度为K的数组，直接来看代码：

// Let's extend the array to get K fliexable          public static int[] FindMaxTwoImproved3(int[] array, int k)          {              if (k < 0) throw new ArgumentException("The K should not be negative.");              if(array != null && array.Length < k) throw new ArgumentException("The K should less than the length of target array.");              if (array == null || array.Length == 1) return array;              // Here is a bug when the max value is negative since the initial value in the int array is 0              int[] result = new int[k];              // This is to fix the bug above              for (var index = 0; index < result.Length; index++)              {                  result[index] = int.MinValue;              }              for (int index = 0; index < array.Length; index++)              {                  if (array[index] >= result[k - 1])                  {                                      // 这个for循环是文中提到的高亮部分                    for (int fallback = 0; fallback < k - 1; fallback++)                      {                    result[fallback] = result[fallback + 1];                    }                    result[k - 1] = array[index];                  }                  else                  {                      for (int fallback = k - 1; fallback >= 0; fallback--)                      {                          if (array[index] >= result[fallback])                          {                                                      // 这个for循环是文中提到的高亮部分                            for (int fallback2 = 0; fallback2 < fallback; fallback2++)                                                            {                                  result[fallback2] = result[fallback2 + 1];                              }                            result[fallback] = array[index];                          }                      }                  }              }              return result;          }

在这段代码中，大家有没有发现有代码重复的嫌疑？我把他们高亮起来了。我们再定义一个公共方法，

/// 
        /// 改方法会负责将当前数组array从前往后的K-1个数字依次赋值成后面的数组，        /// 而最后一个值我们将替换成target        /// 
        ///         ///         ///         public static void Fallback(int[] array, int target, int k)        {            if (k > 0)            {                for (int fallback2 = 0; fallback2 < k - 1; fallback2++)                {                    array[fallback2] = array[fallback2 + 1];                }                array[k - 1] = target;            }        }

将高亮部分也替换一下，看最后的代码：

// Let's remove the duplication code         public static int[] FindMaxTwoImproved4(int[] array, int k)         {             if (k < 0) throw new ArgumentException("The K should not be negative.");             if (array == null || array.Length == 1) return array;             // Here is a bug when the max value is negative since the initial value in the int array is 0             int[] result = new int[k];             // This is to fix the bug above             for (var index = 0; index < result.Length; index++)             {                 result[index] = int.MinValue;             }             for (int index = 0; index < array.Length; index++)             {                 if (array[index] >= result[k - 1])                 {                     Fallback(result, array[index], k);                     result[k - 1] = array[index];                 }                 else                 {                     for (int fallback = k - 1; fallback >= 0; fallback--)                     {                         if (array[index] >= result[fallback])                         {                             Fallback(result, array[index], fallback);                             result[fallback] = array[index];                         }                     }                 }             }             return result;         }

大家发现了吗？这是不是我们见过的一种排序算法。没错，当K = N 时，这就是开辟了新存储空间的插入排序了。有没有？

接下来我们就可以定义各种不同的输入去测试我们的算法啦，这里是一个例子。供大家参考：

static void Main(string[] args)        {            int[] array = new int[5] { -5, -3, -4, -5, 10 };            var result = FindMaxTwo(array);            PrintArray(result);            result = FindMaxTwoImproved4(array, 2);            PrintArray(result);        }        public static void PrintArray(int[] array)        {            if (array == null)            { Console.WriteLine("The array is null or empty"); }            else            {                foreach (var i in array)                {                    Console.Write(i + "  ");                }                Console.WriteLine();            }        }

---

欢迎大家关注我的公众号，还有我的专题系列

• 。

大家有什么更好的解法，也欢迎讨论哈。