算法很美java教程4



# 网址：

《算法很美》视频

数据结构可视化

---

---

• &（与）、|（或）、^（异或）、~（非/取反）
• ~ >>和<<运算符将二进制进行右移或者左移操作
• ~ >>>运算符将用0填充高位

P1：找出唯一成对的数

问题描述：

一个顺序数组中有一个数出现了两次，其他的数仅出现了一次，现在要找出这个重复的数（为保证高效，每个数组元素仅能访问一次）

思路分析：

异或位运算符(返回)，先举个例子：比如11^2的结果为9，先将11与2都转为二进制显示为1011和10补位后为1011和0010，两者的每一位进行逻辑异或，结果为1001，转换为十进制就是9。由此的，两个任意的相同数进行异或后都为零，由此将题目中的数组逐一进行异或，那么重复的那两个数变为0，再创建一个顺序数组，令每个数只出现一次，再逐一进行异或处理，得到那个重复的数

代码实现：

问题思考：

为什么说异或运算符是半加运算符？为何称异或为不带进位的加法运算？

P2：找出落单的数

问题描述：

一个数组中除一个数字出现了一次外，其他的数字都出现了两次，找出落单的数

思路分析：

同上，遍历一遍逐一异或效率最高

代码实现：

略

P3：二进制数中1的个数

问题描述：

输入一个整数，输出此数二进制表示中的1的个数

思路分析：

1. 第一个思路是利用Java基础类将数先转换为二进制数，然后强制转换为字符串类型逐一与一进行对比，但是不太地道。
2. 第二个思路是利用进位运算符将1进位或者将输入的数退位与1做与运算（&），得到结果；
   • 比如9，二进制是1001，先是1进0位——0001，1001&0001就是1（也就是0001）那么可得知这个数（9）的最后一位是1

     然后是1进1位——0010，1001&0010就是0，而不是0010，因为9的倒数第二位不是1。以此类推

   • 输入的数退位也类似，还是9（1001），退i位后与1与运算后再与1相等判定即可确定次数的倒数第i+1位是不是1（1001&0001、0100&0001……）
3. 第三个思路就是让输入的数递减1，再与每次递减前的数做与运算（&），直至此数为零，则做与运算的次数就是1的个数(返回)
   • 比如说10（1010），10（1010）-1（0001）结果是9（1001），1010&1001结果是1000；1000-0001结果是0111，1000&0111结果是0，与运算进行了两次，而1有两个。

代码实现：

P4：是不是2的整数次方

问题描述：

用一条语句判断一个整数是不是2的整数次方

思路分析：

1是2的零次方，1的二进制数是1

8是2的三次方，8的二进制数是1000

32是2的五次方，32的二进制数是

…………

可以知道一个整数是不是2的整数次方即，看这个数的二进制数是否仅有一个1，那么根据之前P3中的第三个思路.，问题一点而破。

代码实现：

P5：将整数的奇偶位互换

问题描述：

将二进制位的奇数位和偶数位呼唤

思路分析：

像是9（1001）换完后为6（0110）

1与任何数做与运算&其结果都为那个数本身，0与任何数做与运算&其结果都为0，可利用这个特征将目标数的奇偶数位分别保存下来，然后进行异或运算得到结果

代码实现：

P6：0~1间浮点实数的二进制表示

问题描述：

给定一个介于0和1之间的实数，类型为double，打印出他的二进制表示

若该数字无法精确地用32位以内的二进制表示，则打印“ERROR”

思路分析：

对于整数的二进制计算方式为：除于2取商

对于浮点数的二级制计算方式为：乘以2取整

代码实现：

P7：出现k次与出现1次

问题描述：

数组中只有一个数出现了1次，其他的数都出现了k次，请输出只出现了1次的数。

思路分析：

首先说不进位加法，在这里可以认为是异或^

两个相同的2进制数做不进位加法结果为0，“任意两个相同的数异或的结果为0”.

十个相同的10进制数做不进位加法的结果为0

k个相同的k进制数做不进位加法结果为0.

我们对上述数组进行k进制的不进位加法，最后得到的将会是单独出现一次的那个数的k进制表示，然后用Integer.toString(i,radix)；转换为十进制即可；

代码实现：

Tips：

话说用map做岂不是更方便？

递归设计经验

• 找重复（找到子问题）
• 找重复中的变化量（参数）
• 找参数的变化趋势（程序的出口）

递归基础练习

求阶乘

顺序打印

数组求和

回溯字符串

斐波那契数列

最大公约数

汉诺塔

二分查找递归解法

arr——查找的数组，low——查找起始下标，high——查找结束下标，key——查找目标

希尔排序

简要来说：希尔排序就是插入排序的优化版本。

插入排序就是对比新数与原数列元素的大小将新数作为新元素插入到数列中其过程可以简述为：

9 5 4 6 8 1——5 9 4 6 8 1——4 5 9 6 8 1——4 5 6 9 8 1—— 4 5 6 8 9 1——1 4 5 6 8 9

希尔排序的思路

如序列{9,8,7,6,5,4,3,2,1}

1. 确定首个增量，通肠胃数组长度的一半
2. 其次利用增量将数列分组，本例中的{9,5,1}{8,4}
3. 然后依次对分组的数列直接使用插入排序

希尔排序相对于简单的插入排序所做的比较和插入动作都少得多，故效率也很高（和快排有得一拼？）

代码实现：

评估算法性能，主要是评估问题的输入规模n与元素的访问次数f(n)的关系，就是列出函数表达式。

大O表示法

大O符号表示忽略掉函数的非主体部分的表示方法

P1：小白上楼梯（递归设计）

问题描述：

小白正在上楼梯，楼梯有n阶台阶，小白一次可以上1阶、2阶或3阶，实现一个方法，计算小白有多少种走完楼梯的方式

思路分析：

还是那个切蛋糕的思想，上n阶台阶=上1阶台阶+上2阶台阶+上3阶台阶

假设现在还有一次上完了n阶台阶，那么最后一次可以是上1阶这种方式，也可以是2、3阶这种方式，考虑这一次，倒数第二次的情况和本次情况相同，这就是重复的问题。想到倒数最后一次上楼梯的方式，也就是方法的出口，倒数最后一次可能有3阶，但是三阶又可以分为2阶和1阶，那么仅考虑2阶和1阶即可——当倒数最后一次有2阶时，有1+1以及其本身直接上2阶共2种方式；当倒数最后一次有1阶时，就只有其本身上1阶1种方式，当最后一次没有楼梯上时理应是0，但通过计算，应该是也包含了上0阶本身1种方式（没完全想透，这样结果是对的，强行解释）。

代码实现：

P2：旋转数组的最小数字（改造二分法）

问题描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小是为1

思路分析：

将数组最开始的若干个元素移动到数组末尾，由于原来的数组是有序递增的，所以旋转后的数组的最大值的右边一定是最小值

代码实现：

代码总结：

二分查找，只是二分的条件变为了判断是否是顺序，当数列进行二分时，最小的数一定在不是顺序排列的那一半，就是利用一直用begin和end中间的数arr[mid]进行判断，顺序排列的那一半的哨兵将会被赋予mid的值，从而抛弃判断那一半，借此不断缩小判断长度，最后仅剩2个，左边begin是最大的，右边end是最小的

这是递推不是递归

P3：在有空字符串的有序字符串数组中查找

问题描述：

有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字符串（肯定不是空字符串）的索引。 2

问题分析：

像上题一样，利用二分法进行查找，只是增加了一个是否为空字符串的判断

代码实现：

P4：最长连续递增子序列（部分有序）

问题描述：

类似于：(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。找出目标数组中最长的递增子序列

思路分析：

其实只需要遍历一遍就可以了

代码实现：

P5：设计一个高效求a的n次幂的算法

常规方法：

利用n进行a的累乘

优化后的方法：

将指数进行倍增来进行快速计算，同时借助了递归。

分治法（divide and conquer，D&C）：将原问题划分为若干个规模较小而结构与原问题一致的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治法的优点之一为：容易确定运行时间

分治法步骤

1. 分解（divide）：将原问题分解成一系列子问题；
2. 解决（Conquer）：递归地解决各个子问题，若子问题足够小，则直接有解；
3. 合并（Combine）：将子问题地结果合并成原问题地解。

快速排序算法：

思路：

1. 分解：数组A[p..r]被划分为两个子数组A[p..q-1]和A[q+1..r]，使得A[q]为大小居中的数，左侧A[p..q-1]都小于等于它，右侧A[q+1..r]都大于等于它。其中计算下标q也是划分过程的一部分
2. 解决：通过递归调用快速排序，对子数组及其后代进行排序
3. 合并：因为子数组都是原址排序，所以不需要合并

快速排序实现：

快排之单向扫描分区法：

图解：

快排之双向扫描法：

思路：

头尾指针往中间扫描，从左找到大于主元的元素，从右找到小于等于主元的元素交换，继续扫描，直到左侧无大元素，右侧无小元素

图解：

代码实现：

快排的优化

一般使用的快排都是使用的是上述的双向扫描法，正常情况下，快排的时间复杂度为n*㏒₂n，但仍旧会有最坏的情况发生，此时时间复杂度仍为n^2，所以有时为了更高效要对快排进行优化处理，以下为一些优化的方法。

快排之三点中值法

思路：

最影响快排效率的就是分界值的确认，三点中值法就是将主元定为首下标元素arr[left]、尾下标元素arr[right]以及中间元素arr[midIndex]的中值，在一定程度上能够对快排进行优化。

1 2 3 、1 3 2、 2 1 3 、2 3 1 、3 2 1、 3 1 2

代码实现：

partitions3（返回）

快排之绝对中值法

绝对中值法的时间复杂度大稳定在2nlgn

思路：

就是将数组中绝对中值的下标作为快排的分界值下标。由于查找绝对中值的下标又需要一定的时间，所以通常大都使用上述的三点中值法

代码实现：

快排之通过插排进行替换优化

思路：

通过计算O(n^2)&O(nlg(n+1))当需排序个数小于8的时候，用插排优化最快，因此在快排时判定一下排序个数是否大于8即可

代码实现：

归并排序算法：

思路：

归并排序算法完全依照了分治模式：

1. 分解：将n个元素分为各含n/2个元素的子序列；
2. 解决：对两个子序列递归地排序；
3. 合并：合并两个已排序的子序列已得到排序结果。

   归并比快排的分解更为随意，其重点是合并 快排的算法复杂度主要在分解，归并的算法复杂度主要在合并

归并排序实现：

此种为将排好序的数填入新空数组temp，然后用temp覆盖原始数组arr

merge方法   (返回)

当然也可以先将原始数组arr备份在temp里，然后用temp作为读取的数组，将元素填入覆盖arr

图解：

P1：奇偶排列

题目描述：

将数组中的所有奇数放于偶数之前，要求时间复杂度O(n)，无大小要求

思路分析：

只需将快速排序双指针法的判定条件修改即可

代码实现：

P2：第K元素

问题描述：

以尽量高的效率求出一个乱序数组中按数值顺序的第K个元素

思路分析：

还记得快排的分治步骤吗？分解——解决——合并，当我们写分解时，即确定数组分界值时，我们会发现，分界值的下标index即为数组中第index大的数，所以当我们想要找第K个元素，只需将K和index的大小关系作为判定条件，来选择递归左半部分还是右半部分即可。

代码实现：

_test.partition3.

P3：超过一般的数字

问题描述：

数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字

​ Tango是微软亚洲研究院的一个实验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？

思路分析：

一个数字出现的次数超过了数组的一半，那么是不是可以说，如果对这个数组进行排序，即使这个数字在数组中时最大的或者最小的，数组最中间的元素一定是它。此题的解法有四：排序后返回arr[N/2]（时间复杂度Nlg(N)）、hash统计（以后会讲）、顺序统计（也就是将P2的K换为arr.length/2）、不同的数进行消除。

代码实现：

1. 排序后返回arr[N/2]

2. hash统计（以后会讲）
3. 顺序统计

4. 不同的数进行消除

   candidate进行记录当前的数，candidate与下一个数字相同，则nTimes+1，若不相同，则nTimes-1，也就是是水帖+1，不是水贴-1，最后遍历一遍结束后，剩下的就是水贴。

   但是如果说水帖数和非水帖数相同，比如说{2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1}那么最后一步就是nTimes=0，candidate=9，然后输出9.以下进行优化

P4：最小可用ID

问题描述：

在非负数组（乱序）中找到最小的可分配的id（从1开始编号）数据量

思路分析：

1. 暴力解法，从1开始查找到到，看每个数是否在数组中，时间复杂度为O(n²) 最大为1×10^12？
2. 先排序然后遍历查询，先将数组从小到大排序，然后遍历查找空缺，时间复杂度为O(nlgn+n)
3. 类桶排解法，创建一个辅助空间，遍历原数组，将辅助空间中下标和原数组个元素相同的元素++（从0变为1），然后遍历辅助空间，找到那个最小为零的辅助空间元素并返回其下标。时间复杂度为O(2n);
4. 二分查找，找东西少不了二分。在本题中，比如说数组为{1,2,3,4,5,6,7,8,10},使用patition找其分界值，如果第一次返回的数恰好等于 (length+1) / 2 ,那么说明左边是稠密的，继而对右边进行寻找，反之对左边进行寻找。

   本数组第一次返回5，等于 (length+1) / 2 = 5，那么左边稠密，对右边查找，然后递归递归……

代码实现：

1. 暴力解法

2. 排序遍历查询

3. 类桶排解法

4. 二分查找

P5：合并有序数组

问题描述：

给定两个排序后的数组A和B，其中A的末端有足够的缓冲空间容纳B，编写一个方法，将B合并入A并排序

思路分析：

思路与归并排序的合并相似，

代码实现：

P6：逆序对个数

问题描述：

一个数列，如果左边的数大，右边的数小，则称这两个数位一个逆序对，求一个数列中有多少个逆序对。

思路分析：

回想之前写的merge方法,仔细看其图解可以看出只需要在其中增加一个计数器，就可以把逆序对的个数求出来，凡是抓取右半部分元素的步骤都说明了逆序对存在，且为左半部分元素的个数（或许当配合递归不太好想）

8，4，5，7，1，3，6，2，

图解:

8 4 5 7 1 3 6 2

先进行分解

8 , 4 5 , 7 1 , 3 6 , 2

进行第一次合并时逆序对为：

8 , 4 6 , 2 数量为2

第一次合并结果：

4 , 5 , 7 , 8 1 , 2 , 3 , 6

进行第二次合并时逆序对为：

4578 , 1 4578 , 2 4578 , 3 78 , 6 数量为14

第二次合并完成，结束

逆序对数共为：16

代码实现：

P7：排序数组中找和的因子

题目描述：

给定已排序数组arr和K，不重复打印arr中所有相加和为K的不降序二元组

ep：输入arr = {-8,-4,-3,0,2,4,5,8,9,10},K = 10;输出(0,10)(2,8);

拓展训练：如果是三元组呢

思路分析：

我首先想到的是类似于归并排序那样二分找，但是会有遗漏，由于题目中已经给定了的条件中有：已排序的数组，那么只需要用两个指针从左右开始移动判定即可

伪代码：

代码实现：

拓展题实现：

只是多加了一个指针，这样会使时间复杂度再度上升到O(n²)级别

P8：需要排序的子数组

题目描述：

给定一个无序数组arr，求出需要排序的最短子数组长度（指定O(n)级别）

ep：输入arr = {2,3,7,5,4,6},返回4，因为只有{7,5,4,6}需要排序

思路分析：

如果先对数组进行排序然后在对比查找，那么时间复杂度会是O(N㏒N+N)，不符合O(N)级别要求

如果这个数组本来是升序，那么第一个减小的数，也就是第一个折点就是需要排序的子数组的起点，那么终点如何寻找呢，需要从后向前找到比折点小的第一个数，期间也需要注意随时更新折点

代码实现：

P9:前K个数

问题描述：

求海量数据（正整数）按逆序排列的前K个数（topK），因为数据量太大，不能全部储存在内存中，只能一个一个地从磁盘或者网络上读取，请设计一个高效的算法来解决这个问题

不限制用户输入数据的个数，用户每输入一个数据就回车使得程序可立即获得这个数据，用户输入-1表示终止输入

然后用户输入K，代表要求的topK，请输出topK，从小到大，空格分隔

思路分析：

之前我们做过求第K小的数的题目，但是那是在数组确定的情况下进行的，而且这种算法没有针对性，占用了过多无用的资源。

在冒泡排序中，我们将大泡泡不停的向后移动，在这道题也可以用这个想法。

经历创建链表，冒泡，输出，链表删除即可

但是这种算法用了两个for循环嵌套，显然时间复杂度是O(n^2)，还不够优

但是思路是没错的，就是需要一个大小为K的空间，每传入一个数，若这个数比空间里的最小数大，就用这个数把空间里的最小数替换掉。那么小顶堆是很适合作为这个大小为K的空间，每次只需将堆顶作为比较和替换的数据即可，然后再次堆化。

代码实现：

Heap.

p10：topK问题

问题描述：

公司现在要对几万员工的年龄进行排序，因为公司员工的人数非常多，所以要求排序算法的效率非常高。

输入人数n，然后输入n个数据

输出排序后的n个数据

1<=n<=

思路分析：

人的年龄范围比较小，所以利用计数或者基数排序比较好，这道题主要要明白在哪些情况下使用那种排序。

代码实现：

P11：最小数组拼接数

问题描述：

输入一个正整数数组，把数组里所有整数拼接起来排成一个数，打印出能拼接处的所有数字中最小的一个。

ep：输入数组{3,32,321}则打印出这3个数字能排成的最小数字为

思路分析：

Java中有Arrays.sort可对各种数据进行排序，同时其中也提供了一个Comparator接口，我们可以将比较的规则重新定义，借以实现某些功能，在这里调用重写Comparator匿名类中的compare方法，原来需要比较的是o1和o2的大小，进行重写后将两者融合然后比较融合后的大小。

如{4，432，43，4321}——4432>4324,>——{4324,}——>——{}

代码实现：

P12：字符串查找

问题描述：

输入两个字符串str1和str2，请判断str1中所有字符是否都存在于str2中

思路分析：

Java中String中indexOf算法中可以返回指定字符在字符串的位置并返回，若没有则返回-1，借用这个就很简单，但是其内部仍旧是遍历数组，时间复杂度是O(n^2)级别，此时若是使用Arrays类中的binarySearch（二分查找）方法就可以将时间复杂度缩小为O(nlogn)级别。

代码实现：

树是一种逻辑结构，另外的例如数组和链表都属于物理结构

根节点之后有子节点，子节点之后有叶子节点，每个根节点都有其左子节点和右子节点，二叉树的下标会从上到下从左到右依次进行顺序排列，计算公式：如果说根节点下标是 i，那么他的左子节点下标为 2 * i + 1 ，右子节点下标为 2 * i + 2 ，如果已知子节点下标 j 求父节点下标，则公式为 (j - 1) / 2 。

树的遍历：

树中一共有三种元素：根节点D、左子树L、右子树R，按照搭配方式来讲，二叉树的遍历共有六种：DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以最终我们只讨论三种方式：

DLR--前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）

LDR--中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）

LRD--后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

代码实现：

堆的概念：

• 二叉堆是完全二叉树或者是近似完全二叉树
  • 完全二叉树就是除了最后一层其他每一层都是完全填满的
  • 近似完全二叉树，是指在完全二叉树的基础上，最后一层以此从右可以空缺一些叶子节点。
• 二叉堆满足两个特性：
  1. 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值
  2. 每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
• 任意节点的值都大于其子节点的值——大顶堆
• 任意节点的值都小于其子节点的值——小顶堆

思路分析：

1. 堆化，反向调整使得每个子树都是大顶或者小顶堆
2. 按序输出元素：把堆顶和最末元素对调，然后调整对顶元素

堆排序引入：

——堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

• 堆排序的基本思想：

  ——堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

代码实现：

1. 堆化Heap(返回topK)

2. 对调元素后减小规模（递归）

思路：

用辅助数组中出现的数字技术，元素转下标，下标转元素

代码实现：

思路：

设计K个桶，然后将n个输入数分布到各个桶中去，对各个桶中的数进行排序，然后按照次序把各个桶中的元素列出来即可。（总感觉和计数排序很相似？？）

桶排序通过分配和收集过程来实现排序

桶排序和计数排序对比：

BucketSort

CountSort

基数排序相当于桶排序的进阶版

思路分析：

简要来说：对于每个数据中的每一位都是0~9的数字，基数排序根据每个数据从个位开始的数据进行桶排序，这样占用空间类似，但是若数据量范围大，数量多，则会大大降低运行时间

基数排序同样需要链表来进行支持

图解：

代码实现：

基础排序

冒泡排序

——大泡泡向上漂浮的快，小泡泡向上漂浮的慢，导致小泡泡在下，大泡泡在上

效率太低，O(n^2)，通常用其内部的循环方式来找最大值和最小值

插入排序

——上体育课，进来一个新同学，要根据他的身高来让他插到队伍之中，如果队伍原本就不需要大调，那么插排是不二之选

平均效率低，但在序列基本有序时很快，有其适合的使用范围

希尔排序

——插入排序的优化，不是一个一个地插入，而是将数组不断分为更小的数组并进行插入排序

类似于8，5，2，3，7，6，4，1。

分为(8，7)、(5，6)、(2，4)、(3，1)进行插排(7，8)、(5，6)、(2，4)、(1，3)

然后分为(7，5，2，1)、(8，6，4，3)进行插排(1，2，5，7)、(3，4，6，8)

然后为1，2，5，7，3，4，6，8，进行插排1，2，3，4，5，6，7，8，避免了最差的情况带来的影响

效率较稳定，但仍旧较慢

分治法

快速排序

快排时软件工程中最常见的常规排序法，其双向指针扫描和分区算法是核心，这些也往往用于解决类似问题，特别地partition算法用来划分不同性质的元素

快排重点在于序列的切分

归并排序

归并排序也是较常用的常规排序法，利用了空间换取了时间

归并排序重点在于子问题的合并

堆排序

堆排序较为特殊，用到了二叉堆的数据结构，是继续掌握树结构的起手式

堆排序可以等同于查排序+二分查找

非比较排序

上面都是基于比较的排序，可证明它们在元素随机顺序的情况下**为NlgN

以下的非比较排序在特定情况下会比基于比较的排序快

计数排序

可以说是最快的排序，使用它来解决问题时必须注意如果序列中的值分布比较广，而数据量较少，则会浪费很多的空间

计数排序的适用情况：序列中的值分布比较集中

桶排序

先分桶，然后用其他的方法对桶内元素排序，按桶的编号依次检出

桶排序的适用情况：序列的值较为均匀的分布在桶中

基数排序

基数排序是KN级别排序（其中K是最大数的位数）是整数数值排序里面又快又稳的，只需开辟固定的辅助空间即可

基数排序的适用情况：大多数的十进制整数排序

排序的期望水准：

1. 准确描述算法过程
2. 能够快速写出伪代码
3. 能分析其时间复杂度
4. 能够灵活运用，对其内部根据要求修改

十种排序的汇总：

P1：顺时针打印二维数组

问题描述：

输入一个数n，顺时针打印n维数组；ep：

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

思路分析：

锻炼逻辑思维的题目，要尽量短的时间有思路并且写出。

打印第一行——打印最后一列——逆打印最后一行——逆打印第一列——转为下一圈直至结束，这样的话要创建四个变量吧，按顺序为左上行增leftUpRow，右上列增rightUpCol，右下行减rightDownRow，以及左下列减leftDownCol。

代码实现：

P2：0所在行列清零

问题描述：

矩阵中某个元素为0，将0所在地行和列清零,例如：

1 2 3 4

5 6 0 8

9 0 11 12

13 14 15 16

转化后为：

1 0 0 4

0 0 0 0

0 0 0 0

13 0 0 16

思路分析：

图例有两个0，如果将第一个0的行列清零，那么清过的0不能再次进行行列清零，要注意这一点

代码实现：

图解：

P3：Z形打印

题目描述：

1 2 3 4

5 6 7 8

9 10 11 12

斜着打印为：1，2，5，9，6，3，4，7，10，11，8，12

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/java-jiao-cheng/14508.html