Java数组、集合、散列表常见算法浅析

作者: 门心叼龙 | 来源:发表于2019-03-24 18:32 被阅读14次

Java数组、集合、散列表常见算法浅析
Java数据结构与算法初级篇之数组、集合和散列表
复习
数据结构必备代码
【集合】Hashmap
常用数据结构
ARTS-第七周
面试必备——Java集合框架
查找（散列表）
散列表算法

数据是基础，算法是灵魂

本文出自门心叼龙的博客，属于原创类容，转载请注明出处。https://blog.csdn.net/geduo_83/article/details/86549897

这篇文章我们只谈算法的具体实现思考过程，并没有相关代码实现，代码的实现过程请参见我的另外一篇文章：Java数据结构与算法初级篇之数组、集合和散列表

源码下载地址：https://download.csdn.net/download/geduo_83/10913510

初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树、图

理论篇：Java数组、集合、散列表常见算法浅析
理论篇：Java栈、队列、链表常见算法浅析
理论篇：Java树、图常见算法浅析

前言：

在2018年9月份，也就是前几个月，阿里巴巴搞了一个全球数学竞赛，一石激起千层浪，各路豪杰纷纷参战，移动互联网的狂潮已经结束了，下一个风口将是人工智能，搞人工智能就离不开数学算法，马云醉翁之意不在酒，而在抢夺全球的顶尖级数学人才，可见算法的重要性。

我们日常开发都在关注界面和用户体验，在算法上往往要求不高，一直有打算写几篇关于算法的文章，我在网上搜索了下，基本都是直接贴算法代码，并没有分析这一步步为什么要这么实现，也许我没有发现，分析很重要，有了思路再去实现也是顺理成章的事情了，所以今天就写下了下面的这些文字。

1.冒泡排序

通过相邻的两个数两两相比来进行排序，其中有两个循环，第一个循环控制循环的轮次，第二个循环控制每一个轮次循环的次数，第一轮循环确定的最后一个元素，第二轮循环确定的是倒数第二个元素，照这样下去，直到确定了第一个元素，则循环排序完毕。

需要注意的是，第一个循环它的结束条件是i < len-1; 第二个循环的结束条件是j < len - i - 1;

2.选择排序

第一步拿出第一个元素和剩余的元素进行比较，确定了第一个元素，第二步拿出第二个元素和剩余元素进行比较，确定了第二个元素，照这样下去，直到确定了最后一个元素，则循环排序完毕。和冒泡排序一样，也是通过两个循环来完成的，第一个循环是控制循环的轮次，第二个循环是控制每一轮循环的次数。

需要注意的是，第一个循环它的结束条件是i < len-1和冒泡排序一样，第二个循环的开始条件是j = i + 1; 结束条件是j < len 。

通过分析我们不难得出结论，无论是冒泡排序还是选择排序，第一个控制轮次的循环的结束条件都是一样的都是len - 1; 第二个控制每一轮循环次数的条件是相反的，冒泡排序控制的是结束条件j < len - i - 1，而选择排序控制的是开始条件j = i + i。

这是我们哲学中讲的矛盾，而冒泡和选择就是我们矛盾的两个方面。

3.桶排序

桶排序的核心思想就是以源数组的值作为新数组的下标找到这个新元素，然后对该元素进行加1赋值。通过遍历源数组对新数组进行加1操作，一轮循环完，排序也就确定了，然后对新数组进行遍历只要发现值大于0的元素就打印它的下标，而打印的值就是我们想要的结果。

需要我们注意的是桶排序是有前提条件的必须要知道源数组中的最大元素才行，因为只有知道最大元素才能确定新数组的长度。

桶排序的效率是非常高的，但是如果源数组的值是不均匀的那么势必会造成空间的浪费，桶排序就是典型的以空间换时间的最佳范例。

4.判断一个数组中有没有重复元素

说到元素重复我们自然会想到数组、集合，这两种数据结构都是允许重复数据的，而散列表是不允许有重复数据的。

我们想了如果我们遍历数组中的元素，把这些元素存储在散列表当中将会何如？有的人会说去重复了，是的没有错，但更重要的是我们在将数组的元素往散列表里面存入的时候加一个是否该元素在散列表中是否存在的判断不就完了吗？如果散列表中没有耶就直接存储了，如果有也就直接返回了，就这么简单。

这一招需要我们对散列表的知识非常的了解，其实对于集合和散列表都有contains这个方法。

5.删除数组中的重复元素

通过我们对上面判断一个数组中是否有重复元素的分析，再做这个题就非常的简单了，直接用用一个散列表就ok了。

有没有其他的解决方案？有没有不借助其他的数据结构直接就能实现的方案？有，其实方案的中心思想就是选择排序有点像，就是取出当前元素和其他剩余的元素进行对比，如果有相等的则将后面的所有元素往前移动一个位置，移动完毕在对源数组的长度进行减1的压缩处理，压缩完毕在从头开始循环判断。

这个方法就注意两点，首先只要相等就把后面的所有元素往前移位，然后移动完毕在对源数组长度进行减1的压缩处理，压缩完毕重新开始循环。

6.求数组中任意两数之和等于目标数的元素的下标

说到两数之和，那么就会想到数组中的任意两个元素都会碰一下求和和我们的目标数对比一下如果相等就把这两个元素的下标返回，这就把问题解决了。

任意两个元素都要碰一下，此时我们又想到了选择排序，通过这个算法我们就能实现两两相碰。两个循环一个判断就能问题解决。

还有另外一种算法，首先我们可以新建一个新的数据对象，还对象有两个字段，一个存下标，一个存元素的值，接着通过源数组建立一个以新数据对象为元素的数组并对该数组进行排序，然后声明两个指针，一个头指针，一个尾指针，这两个指针分别从数组的头和尾进行前进移动和回退移动，每移动一步求和，和目标数进行对比，如果小于目标数则头指针往前移动，然后再求和对比，如果大于目标数则尾指针回退移动再求和对比，直到相等就将两个对象的下标返回就解决问题了。

这两种算法各有优劣，方案1当然代码量最少是最简单的，方案2让我们感受到了指针在运算中神奇作用，虽然代码量有些大，但是思路还是很清晰的。

7.从左上到右下的路径数

这道题大意是这样的，已知给定了一个m*n的二维数组，以第一个元素作为开始点，以最后一个元素作为结束点，然后开始点开始移动，并且只能往右往下移动直到到达结束点，求一共有多少条路径数？

看到这道算法题想必有很多人都会懵圈，真是老虎吃天无从下手，这背后到底有什么样的逻辑关系？会用到哪些数据结构？用到什么样的循环？用到什么样的判断？

其实具体的思路是这样的，声明一个m*n的二维数组，初始化赋值都为0，接着给数组的第一行赋值为1，然后给数组的第一列赋值为1，最后一步给数组中剩余的其他所有元素赋值，其他元素的值为它正上方元素的值和它正左方元素的值之和，赋值完成之后最后一个元素arr[m-1][n-1]的值就是我们所要计算的路径数，一脸懵逼，为什么？为什么通过这样的赋值就是我们想要的计算结果路径数？其实这就是算法中动态规划的问题。

我们把第一行个第一列都赋值为1，为什么？，如果只有一行或只有一列这两种情况都只有一条路，因此赋值为1没毛病，这是合乎逻辑的，然后我们开始移动，每走一步无外乎有两种方案，要么往前走，要么往下走，那么走到当前格子就有两种方案，而这个值正是它正上方元素和正左方元素的和，那么同样道理其他格子的值以此类推，而最后一个元素arr[m-1][n-1]的值就是我们所要计算的路径数。

这就是动态规划其中的奥妙之处，通过三个循环简简单单的解决了我们的问题。

8.求左上到右下路径的最小值

这个问题是上面求路径数问题的扩展，求最小路劲数，不同的是现在还是一个m*n的二维数组，不过这个数组每个元素都已经赋值了，让你求路径上所有元素的和的最小值，从左上到右下的路径有n多条，但是肯定有一条的和值是最小的。其实这还是一个动态规划的问题。

具体解决思路如下，首先声明一个大小完全相同二维数组，现在要给其赋值，赋值完毕我们要的结果也就出来了，第一个元素的值就是源数组第一个元素的值，第一行其他元素的值就是当前元素的前导元素的值和源数组这个位置元素的值的和，第一列其他元素的值就是他的前导元素的值与源数组这个位置元素的值的和，然后其他元素的值就是当前元素上方元素和左方元素取最小值和源数组这个位置元素的值求和，其他元素得计算方式以此类推，直到赋值完成，而最后一个元素的值就是我们要计算的左上到右下路径的最小值。

通过分析我们不难发现，不管是求路径数，还是求路径的最小值，其背后的核心思想都是动态规划。通过对数组的动态的赋值计算，从而得到我们要计算的结果。

9.自定义一个集合

集合我们知道他是一个变长数组，只有变长才能源源不断的往里面存放数据，通过集合元素添加流程图我们也能看到，首先需要初始化一个数组，然后在添加元素的时候如果源数组满了就需要扩容了，当然扩容的系数有的是2倍，有的是0.75倍，这由自己定，不管是数组的扩容还是压缩都用到了数组工具类中非常重要的一个方法Arrays.copy(),有了添加的方法，必然少不了删除方法，删除的思路也很简单，就是把要删除的元素之后的元素都往回移动一位，然后再把最后一个元素赋值为0再退出循环就ok了。

10.删除集合中的偶数

很多初学者看到这个问题都觉的太简单了，不就一个循环就解决问题了吗？其实这是有大问题的，问什么？你想了循环开始的时候循环结束的条件就已经确定了，如果你在循环的过程中删除了一个元素，那么数组长度就变短了，而我们循环并没有停止，当循环走到最后的时候势必会造成数组下标越界的空指针异常，怎么办？其实我们通过集合迭代器来做这个删除的工作就可以完美的规避这个问题。因为迭代器不需要下标，也就不存在数组下标越界的问题。