美团一面：如何高效地将两个有序的数组合并成一个有序数组

大家好，欢迎来到IT知识分享网。

在说这个题目之前先来说说一个排序算法 “归并算法”

归并算法采取的思想是分治思想，分治思想简单说就是分而治之，将一个大问题分解为小问题，将小问题解答后合并为大问题的答案。乍一看跟递归思想很像，确实如此，分治思想一般就是使用递归来实现的。

但是需要注意的是：递归是代码实现的方式，分支属于理论。接下来看一副图理解下：

说完它的思想：我们再来分析下时间复杂度。

归并算法采用的是完全二叉树的形式。所以可以由完全二叉树的深度可以得知，整个归并排序需要进行log2n次。然后每一次需要消耗O{n}时间。所以总的时间复杂度为o{nlog2n}。归并排序是一种比较占用内存，但是效率高且稳定的算法

贴上代码：

static void Main(string[] args) { int[] arr = new int[] { 14,12,15,13,11,16 ,10}; int[] newArr = Sort(arr, new int[7], 0, arr.Length - 1); for (int i = 0; i < newArr.Length - 1; i++) { Console.WriteLine(newArr[i]); } Console.ReadKey(); } public static int[] Sort(int[] arr, int[] result, int start, int end) { if (start >= end) return null; int len = end - start, mid = (len >> 1) + start; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; Sort(arr, result, start1, end1); Sort(arr, result, start2, end2); int k = start; //进行比较。注意这里++是后执行的，先取出来数组中的值然后++ while (start1 <= end1 && start2 <= end2) result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; //将每个分组剩余的进行复制 while (start1 <= end1) result[k++] = arr[start1++]; //将每个分组剩余的进行复制 while (start2 <= end2) result[k++] = arr[start2++]; for (k = start; k <= end; k++) arr[k] = result[k]; return result; } 

说完了归并算法回到题目上来 首先分析下 题目给定的是两个已经排好序的数组合并，关键字“合并”，“两个”，正好符合我们的归并算法，并且已经分类好了，只需要去合并就可以了。来看下几张图。推荐：Java进阶视频资源

蓝色的箭头表示最终选择的位置，而红色的箭头表示两个数组当前要比较的元素，比如当前是2与1比较，1比2小，所以1放到蓝色的箭头中，蓝色的箭头后移，1的箭头后移。

然后2与4比较，2比4小那么2到蓝色的箭头中，蓝色箭头后移，2后移，继续比较…….

归并思路就是这样了，最后唯一需要注意的是那个先比较完的话，那么剩下的直接不需要比较，把后面的直接移上去就可以了，这个需要提前判定一下。

贴上代码：

static void Main(string[] args) { int[] arr1 = new int[] { 2, 3, 6, 8 }; int[] arr2 = new int[] { 1, 4, 5, 7 }; int[] newArr = Sort(arr1, arr2); for (int i = 0; i < newArr.Length - 1; i++) { Console.WriteLine(newArr[i]); } Console.ReadKey(); } public static int[] Sort(int[] arr1,int[] arr2) { int[] newArr = new int[arr1.Length + arr2.Length]; int i = 0, j = 0, k = 0; while (i < arr1.Length && j < arr2.Length) { if (arr1[i] < arr2[j]) { newArr[k] = arr1[i]; i++; k++; } else { newArr[k] = arr2[j]; j++; k++; } } while (i < arr1.Length) newArr[k++] = arr1[i++]; while (j < arr2.Length) newArr[j++] = arr2[j++]; return newArr; } } 

感谢阅读，希望能对你有所帮助 :)

来源：blog.csdn.net/weixin_/

article/details/

●【练手项目】基于SpringBoot的ERP系统，自带进销存+财务+生产功能

●分享一套基于SpringBoot和Vue的企业级中后台开源项目，代码很规范！

●能挣钱的，开源 SpringBoot 商城系统，功能超全，超漂亮！

源码获取方式：关注小编+转发文章+私信【666】免费获取
重要的事情说三遍，转发+转发+转发，一定要记得点赞转发哦!!!

在网上搜索HashMap中变量modCount的作用时，大部分的解释都是这样：

Fail-Fast 机制

我们知道 java.util.HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount域，modCount 顾名思义就是修改次数，对HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 Map：注意到 modCount 声明为 volatile，保证线程之间修改的可见性。

这个解释有放在JDK5和JDK6的时候，也许是正确的，因为在JDK5和JDK6中变量modCount确实声明为volatile。但在JDK7和JDK8中，已经没有这样声明了！！！！！

下面是JDK5、JDK6、JDK7和JDK8的源码：

1.JDK5源码截图

2.JDK6源码截图

3.JDK7源码截图

4.JDK8源码截图

我的思考

难道到了JDK7和JDK8中就不需要使用modCount变量，防止使用迭代器的过程中有其他线程修改了map？？？？？

我的思考是这样的：注意看变量modCount的注释中让我们See ConcurrentModificationException，那么我们就找到ConcurrentModificationException异常，在该异常的注释中，有这样一段描述。

Note that this exception does not always indicate that an object has been concurrently modified by a <i>different</i> thread. If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will throw this exception. 

大致翻译如下：

请注意，此异常并不总是表示对象已被其他线程同时修改。如果单个线程发出一系列违反对象约定的方法调用，则该对象可能会抛出此异常。例如，如果线程使用有fail-fast机制的迭代器在集合上迭代时修改了集合，迭代器将抛出此异常。

通过这段对ConcurrentModificationException异常的描述，我有以下看法：

1. 该异常不单单会在多线程情况下发生；
2. 在单线程情况下也可能发生，就是在有使用有fail-fast机制的迭代器遍历集合时，有修改集合的操作也会抛出此异常；
3. HashMap中的modCount是为了结论2而设计的。