剑指offer(一)：数组篇(python)
最近准备找工作，一直在学习/刷一些面试题，目前在看剑指offer这本书，想对最近看的面试题做一些总结，整个系列都是用python语言实现的，写的有什么不到位的地方多多包涵同时欢迎指正，本系列不是按照原书中的章节从面试题1-面试题68的顺序来写的，而是将题目分成了数组、字符串、树结构、链表、位运算、队列、动态规划等不同的专题。
数组作为一种基本的数据结构，其在面试中考察的几率很高，有关数组的可考察的点也比较多，本篇文章总结整合了剑指offer中数组相关的面试题，内容可能一次写不全，会根据时间后续不断的进行补充，接下来的内容是面试题目。
1. 剑指offer第3题：数组中重复的数字
这道题目的题目描述和代码实现见下图：
在上面的例子[2,3,1,0,2,5,3]中，当i = 0时，numbers[0] = 2，下标和下标处的数不相等，将数值2调整到索引2位置处，也就是交换2和1的位置，数组变为[1,3,2,0,2,5,3]；number[0] = 1，下标和下边处的数还是不等，将数值1调整到索引1处，交换得到数组[3,1,2,0,2,5,3]；numbers[0] = 3，将数值3调整到索引3处，交换得到数组[0,1,2,3,2,5,3]；当i = 1、2、3时下标都和下标处对应的值相等，不需要交换；number[4] = 2，下标和下标处的值不相等，将数值2调整到索引2处，但是发现索引2处的数值也是2，那么就有numbers[4] = numbers[2]，返回2，2就是重复的那个数字。
在这道题目基础上还有道变形题目，题目描述和代码实现见下图：
以上面的[2,3,5,4,3,2,6,7]为例，取1-7的中间值为4，计算1-4区间的数字的个数，有[2,3,4,3,2]这5个数字，所以在1-4中存在重复数字，再取1-4区间的中间值为2，计算1-2区间的数字的个数，有[2,2]这2个数字，注意，这时候程序是检查不出来2为重复数字的，它只能判断1-2的数字一共有两个，具体是这两个是[1,1]、[2,2]或者[1,2]它是无法判断的，所以认为在1-2区间是没有重复的，那么此时取计算3-4区间的中间值为3，计算3-3区间的数字的个数，发现count = 2，所以重复值就是3。将其返回即可。
2. 剑指offer第4题：二维数组中的查找
这道题目的题目描述和代码实现见下图：
我们以要查找的数字9为例， 查找从矩阵的右上角开始，因为15大于9，且15下边的元素都比15大，那么整个15这一列可以被舍弃，下次查找在15左边的4列中进行；接着从右上角元素11开始，11还是大于9，同样的舍弃11所在的列，下次查找在11左边的3列中进行；同样从右上角元素7开始，7小于9，由于7左边的元素都比7小，且7右边的元素已经被舍弃，所以可以舍弃7所在的行，下次查找在7下边的4行中进行；同样从右上角元素8开始，8还是小于9，舍弃8所在的行，下次查找从8下边的3行中进行；从右上角元素9开始，此时9和目标元素相等，返回True，即所要寻找的元素9在二维数组中。具体的实现如下：
3. 剑指offer第11题：旋转数组的最小数字
这道题的题目描述和代码实现见下图：
4. 剑指offer第21题：调整数组顺序使奇数位于偶数前面
这道题的题目描述和代码实现见下图：
这道题目使用了3中解法，首先第一种解法是调用了python中的内置函数sorted函数，这种一行代码就可以完成，但是面试的时候这么写显然是不可行的，之所以还把这种解法写出来，就是想多提供一种解题的方案，有关sorted函数的使用，我在这篇文章中做出了详细的说明； 第二种方法就是比较常规的方法，但是此方法的空间复杂度较高，需要新定义两个数组left和right；第三种方法是最优的方法，以上面的数组[20,19,3,10,11,100]为例，对方法3的实现做具体说明，如下图所示：
开始时begin指向数组首元素20，end指向数组末元素100，如图(a)；因为end指向的数为偶数，所以end减1，其指向倒数第二个元素11，如图(b)；end指向的数为偶数且begin指向的数为奇数，所以调换两个数的位置，如图(c)；此时begin指向的数为奇数，其后移到19,19还是奇数，继续后移直到后移至10，同样的end指向的20为偶数，前移到10继续前移直到指向3，如图(d)。但是此时begin>end，所以不再进行交换，直接返回数组，最终得到[11,19,3,10,20,100]。
5. 剑指offer第29题：顺时针打印矩阵
这道题目的题目描述和代码实现见下图：
关于这道题做以下说明：
以题目描述中的4*4矩阵为例，我们要做的就是按照图中箭头的方向从外往内打印矩阵元素。
note1：在printMatrixCW函数中，代码的第25行中的while循环的条件表达式：rows > 2*start and columns > 2*start. 为什么是大于2*start，因为随着顺时针打印矩阵中的元素，循环一次，顺时针打印一圈，start是+1增长的，而矩阵的行数和列数是每圈-2递减的，所以只有将矩阵的行列数大于2倍的start时，才会进入循环进行下一次打印。
note2：printMatrixInCircle函数是完成顺时针打印一圈的功能，如果把矩阵的行看成X轴，列看成Y轴的话，那么矩阵的第一个元素就是原点，X轴右边是正方向，Y轴下面是正方向，那么endX就表示X轴的最大坐标，endY表示Y轴的最大坐标，当顺时针打印一圈后，X，Y轴的最大坐标各减1，也就是endX和endY的值各减1。
6. 剑指offer第39题：数组中出现次数超过一半的数字
这道题的题目描述和代码实现见下图：
7. 剑指offer第42题：连续子数组的最大和
这道题目的题目描述和代码实现见下图：
关于这道题的解题思路可以在下面的表格中体现：
|
|
操作 |
累加的子数组的和 (curr_sum) |
最大子数组和 (max_sum) |
|
1 |
+1 |
1 |
1 |
|
2 |
-2 |
-1 |
1 |
|
3 |
抛弃前面的累加和 +3 |
3 |
3 |
|
4 |
+10 |
13 |
13 |
|
5 |
-4 |
9 |
13 |
|
6 |
+7 |
16 |
16 |
|
7 |
+2 |
18 |
18 |
|
8 |
-5 |
13 |
18 |
当子数组的累积和小于0时就将其抛弃，令累加子数组的和为数组的当前元素，将最大子数组和记录在max_sum中，当curr_sum大于最大子数组和max_sum时，将curr_sum赋值给max_sum，最后返回max_sum.
在此题上进一步要求，如果我们不仅要求max_sum，而且还需要打印使得累积和最大的子向量，那应该怎么做呢，过程如下表所示：
|
步骤 |
操作 |
累加的子数组的和 (curr_sum) |
最大子数组和 (max_sum) |
累加和最大子向量 (sub_arr) |
|
1 |
+1 |
1 |
1 |
[ 1] |
|
2 |
-2 |
-1 |
1 |
[1,-2] |
|
3 |
抛弃前面的累加和 +3 |
3 |
3 |
[3] |
|
4 |
+10 |
13 |
13 |
[3,10] |
|
5 |
-4 |
9 |
13 |
[3,10,-4] |
|
6 |
+7 |
16 |
16 |
[3,10,-4,7] |
|
7 |
+2 |
18 |
18 |
[3,10,-4,7,2] |
|
8 |
-5 |
13 |
18 |
[3,10,-4,7,2] |
可以看到，在程序刚开始的时候curr_sum = 0，我们把索引0添加到index_start中，在刚进入步骤3的时候，curr_sum = -1 < 0，我们同样将索引2添加到index_start中，此后curr_sum一直大于0，所以index_start = [0,2]；同样的道理，我们在curr_sum >= max_sum时，将这些索引添加到index_end中，最终可以得到index_end = [0,2,3,5,6]，我们取index_start中的最大值2和index_end中的最大值6，原数组索引2-索引6对应的元素组成的子数组即为所求。具体代码实现如下：
8. 剑指offer第45题：把数组排成最小的数
这道题的题目描述和代码实现见下图：
数组中元素的数据类型是int型，如果要组合的两个数很大但在int能表示的范围内或者数组中的元素很多，最终的数都会导致溢出，所以我们首先要把int数转换为字符串。 可以看到上面的array2中的数字组成的最小数已经溢出的int能表示的范围，但是转化为字符串后还是能表示这个数。我们以上面的例子[3,32,321]为例对上述代码做个简单的描述：将数组array1中的int数都转化为str类型并保存到strarr数组中得到['3','32','321']，接下来有两个for循环，第一个for循环中的i的取值从0-len(strrarr) - 2，此处也就是0-1，第二个for循环中j的取值从i+1 - len(strarr)-1，也就是1- 2；首先i取0，j取1，比较strarr[0] + strarr[1] 和strarr[1]+strarr[0]的大小，即'332'和'323'的大小，显然'332'>'323'，调换'3'和'32'的位置，数组变为['32','3','321']，此时j + 1即j取2，比较strarr[0] + strarr[2]和strarr[2]和strarr[0]的大小(注意：此时的strarr[0]已经变成了'32')，即'32321'和'32132'的大小，显然'32321'>'32132'，调换'32'和'321'的位置，数组变为['321','3','32']，此时j已经不能再继续取值了，内循环结束，经过一次外循环确定了索引0处的元素(一次外循环确定一个位置处的元素)，此时i+1，即i取1，确定索引1处的元素，依次类推直到外循环结束，最终会得到新的数组['321','32','3']，最后通过.jion将数组中的元素连成字符串并返回。
9. 剑指offer第51题：数组中的逆序对
这道题目的题目描述和代码实现见下图：
其中解决方案三的时间复杂度为O(nlogn)，但是使用了辅助空间，故其空间复杂度为O(n) 。解决方法三的思想和归并排序类似，其图解如下：
10. 剑指offer第53题：在排序数组中查找数字
这道题的题目描述和代码实现见下图：
11. 剑指offer第56题：数组中数字出现的次数
这道题的题目描述和代码实现见下图：
12. 剑指offer第66题：构建乘积数组
这道题目的题目描述和代码实现见下图：
在题目描述中，限制了此处不能使用除法，不然问题将会变得很简单，首先我们先算出数组A中所有元素的成绩mul，那么B[i] = mul/A[i]，从而得到B[i]。但是当A[i] = 0 时，此方法将会失效。数组B可以由如下矩阵创建：
可以看到，矩阵的第i行元素的乘积为B[i]，对角线将矩阵分成两个部分，上述代码中的第一个for循环自上向下求解的是下三角矩阵各行中的乘积，即得到B = [1，1，2，6，24]；第二个for循环中的temp自下向上求解的是上三角矩阵各行中的乘积，然后再通过temp与B[i]相乘最终得到整个矩阵每一个中各元素的乘积即B = [120,60,40,30,24]。