参考资料:
备注:
《剑指offer》上所有题目都应该力求达到选择排序法的熟悉度。
数组(共12道题目):
1、二维数组中的查找(08.19)
6、旋转数组的最小数字(08.20)
13、调整数组顺序使奇数位于偶数前面(08.21)
19、顺时针打印矩阵(08.22)
28、数组中出现次数超过一半的数字(08.23)
30、连续子数组的最大和(08.24)
32、把数组排成最小的数(08.25)
35、数组中的逆序对(08.26)
37、数字在排序数组中出现的(08.27)
40、数组中只出现一次的数字(08.28)
50、数组中重复的数字(08.29)
51、构建乘积数组(08.30)
1、二维数组中的查找
题目描述:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
错误思路:
正对角线二分法:
1 2 8 9 10
2 4 9 12 13
4 7 10 13 14
6 8 11 15 16
7 9 12 16 17
不一定是n*n的矩阵,找不到正对角线;
即便是n*n的矩形,即便能够定位到大于4,小于10,但可能的数据不只是:8、9、4、7,还可能是:9、10、12、13、6、8、7、9即每一个数只对其左上和右下的数据负责(从矩阵生成的角度看),不对左下和右上负责。
解题思路:
补充知识点:python二维列表、python类和对象;
1 | #python |
1 | //java |
6、旋转数组的最小数字
题目描述:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
解题思路:
巧用二分搜索。设立3个指针,low、mid和high。如果array[mid]>array[high],则array[mid]必定属于前半非递减数组{3,4,5},这个时候low和mid之间的元素便都可以排除(因为我们要找的是第二个数组中的第一个元素),low=mid。如果array[mid]
特殊情况:因为给的是非递减元素。所以会出现:三者全相等的情况和三者不全相等的情况。
1.array[low]==array[mid]==array[high]。对应的例子:mid在第一个数组中{2,2,2,1,2}、mid在第二个数组中{2,1,2,2,2}这个时候无法判断array[mid]属于第一个数组还是属于第二个数组,即无法判断应该是:low=mid还是high=mid。无法收敛。对于这种情况,只能遍历数组找到最小值。注意:这种情况的判断一定要放在二分搜索的前面,因为二分搜索未排除这种情况。如果要放在二分搜索的后面,则二分搜索需要添加一个if条件。
2.对于三者不全相等的情况又可以分为两种情况:不相等的那个元素和剩下的数组组成一个数组和两个数组的情况。
当array[low]==array[mid] 且array[mid]!=array[high]时,对应例子:{4,…x…,4,…y…,z}由于:当z=5时,说明该数组没有旋转。(因为一旦旋转,最后一个元素只能<=第一个元素,不可能大于第一个元素(这是由原数组是非递减数组而决定的)。这个时候不能用二分搜索找最小元素了,因为我们无法根据array[mid]和两端元素比较的大小情况来判断最小元素在其左边还是右边(换句话说:在while循环中,if (array[mid] <= array[high])和 if (array[mid] >= array[low])两个条件都符合,无法收敛,旋转数组(至少移动一个元素的情况)中之所以可以用二分搜索是因为:我们可以根据array[mid]和两端元素的大小情况来判断最小元素在其左边(array[mid]属于第二个数组)还是右边(array[mid]属于第一个数组),即if (array[mid] <= array[high])和 if (array[mid] >= array[low])两个条件只有一个符合,这也是二分搜索的核心)。当z=3时,说明该数组旋转了,此时可以用二分搜索。
当array[low]!=array[mid] 且array[mid]==array[high]时,和上述分析类似,此处不再赘述。
补充证明:
命题:在array[low]==array[mid] 或 array[mid]==array[high](三者不全相等)的情况下,相等元素一定属于同一数组。
这也是对于{4,…x…,4,…y…,z}的情况,如果z=3时,能用二分搜索的一个前提。只有证明了这个前提,即{4,…x…,4}必定是一个数组中的元素,{4,…x…,4,…y…,3}才能令low=mid,把low和mid中的元素全部排除(应为low和high只能分别在各自的数组中,如果无法证明,{4,…x…,4}属于同一个数组,low就可能跳到后一个数组中)。
证明:第一种情况:array[low]==array[mid] 且array[mid]!=array[high]时,对应例子:{4,…x…,4,…y…,z}。当z=3时,若中间的4属于第二个数组,则不满足原数组非递减的要求,所以中间的4和第一个4必定都属于第一个数组(证明了low不会跑到第二个数组中去)。所以满足while循环中的第二个if,向后收敛。当z=5,则是原数组,相等元素必定时同一数组,但无法用二分搜索,因为不会收敛。
第二种情况:array[low]!=array[mid] 且array[mid]==array[high],和上述情况类似,此处不再赘述。
1 | #python |
1 | //java |
13、调整数组顺序使奇数位于偶数前面
题目描述:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
解题思路:
设两个指针,第一个始终指向已经处理好的元素的下一个位置(其前面都是筛选过的元素),第二个指向未筛选元素中第一个符合条件的元素,然后这两个指针之间的元素统一后移一位,然后把未筛选元素中第一个符合条件的元素插入到第一个指针的位置,第一个指针的位置后移,第二个指针继续从第一个指针的位置开始向后搜索。
1 | //java |
19、顺时针打印矩阵
题目描述:
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解题思路:
把矩阵作为一个一个的圈,每一圈的四个顶点都可以由该圈的标记j(从0开始计数)确定:左上:(j,j);左下:(matrix.length-1-j,j);右上:(j,matrix[0].length-j-1);右下:(matrix.length-1-j,matrix[0].length-j-1)。用四个for循环即可打印。四个顶点的打印规则要注意:左上和右上在上边打印的过程中打印,右下在右边打印的过程中打印,左下在下边打印的过程中打印(这样处理主要是为了方便处理最后只有一列或者一行的情况)。
圈数的计算方法:(min(matrix.length,matrix[0].length)+1)/2。这是由总结规律而得到的。
只有一列或者一行的情况:无论是最后只有一列或者一行的情况,还是矩阵本身就只有一列或者一行,上边和有右边正常打印。下边只有在其所在的行和上边所在的行不是一列的时候打印(j<matrix.length-1-j),左边也只有在其所在的列和右边所在的列不是一列的时候打印(j<matrix[0].length-1-j)。
1 | //java |
28、数组中出现次数超过一半的数字
题目描述:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如:输入如下所示的一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
解题思路:
采用阵地攻守的思想:任意时刻只能有同一类元素站在阵地上。第一个数字作为第一个士兵,守阵地;num = 1;遇到相同元素,num++;遇到不相同元素,即为敌人,同归于尽,num—;当遇到count为0的情况,又以新的元素值作为守阵地的士兵,继续下去,到最后还留在阵地上的士兵,有可能是主元素。(如果主元素的数量大于一半,则一定是主元素,否则任何元素都有可能留到最后。)再加一次循环,记录这个士兵的个数看是否大于数组一半。
所以最终的target有两种情况(最后的for循环就是为了区分这两种情况):
1.target的数量超过数组长度的一半,这个target正是我们想要找到的;(可以用反证法证明:如果数组中存在一个元素,它的数量超过数组长度的一半,最后的target一定是该数)
2.其他不确定数字,且不一定是数量最多的数。比如:{2,2,2,1,1,3,3},最后target=3,而3不是数量最多的;
命题:如果数组中存在一个元素,它的数量超过数组长度的一半,最后的target一定是该数
证明:用反证法。设该数为x,其数量为numx,其他数为y,其数量为numy。numx>numy。假设最后的target的值不是x,则x全部被干掉了,而干掉一个x需要消耗一个y元素。所以至少需要numx个y元素:{1,2,1,3,1,4},一个y干掉一个x最后一个元素是y,才能保证最后的数是y。而y元素的数量numy<numx,所以必定不会出现target=y的情况。
1 | //java |
30、连续子数组的最大和
题目描述:
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)。
解题思路:
此题为《计算机算法设计与分析》一书中动态规划一章中的例题:最大子段和。书中给出了4种解法,最好的便是动态规划的解法,只需O(n)的时间复杂度:
1.穷举法。把所有子段列出来,找到最大的子段。i可取:0—n-1,j可取:0—n-1,一共有(n-1)(n-1)种情况。每一个子段又需要一个循环来求和,所以需要三个for循环,时间复杂度为:O(n^3);
2.改进的穷举法。以i开头的所有子段的和可以由上一以i开头的字段和在加上array[j],不必再从i开始计算,如此便可省去求每一个子段的那个循环,只需要两个for循环,时间复杂度为:O(n^2);
3.分治算法。不做详细讨论,其时间复杂度为:O(nlogn);
4.动态规划。改进的穷举法是找到:以i开头的子段的特点。而动态规划算法是找到:j结尾(包括j)的子段的特点。和最大的子段必定是以某个j结尾的,并且包括j。对于j的n种情况,求出以j结尾,并且包括j的子段的和,n个数中最大的那个数便是原数组的最大子段和。看上去似乎和穷举法相同,只不过穷举法是对于i的n中情况,求出以i开始,并且包括i的子段的和,n个数中最大的那个数便是原数组的最大子段和。而动态规划从j着眼的算法中,巧妙利用相邻两个j的最大子段和(以j结尾,并且包括j)之间的关系,省去了两层循环(开头i的循环和确定i和j之后求和的循环),把时间复杂度降低到:O(n);着实巧妙。
动态规划递归式:b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n;其中b[j]:以j结尾并且包括j的子段的最大和。当b[j-1]>0时,b[j]=b[j-1]+a[j],当b[j-1]<0时,b[j]=a[j];
1 | #python |
1 | //java |
32、把数组排成最小的数
题目描述:
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
解题思路:
1.全排列,然后找出最小的数。时间复杂度为:O(n!);
2.把数组中的元素处理为字符串,然后按照字典序进行排序,数组中的字符按顺序组成的数即为最小的数,可以用反证法证明。此时时间复杂度取决于排序算法的时间复杂度。这里注意的是字符串的比较函数需要重新定义,不是比较a和b,而是比较ab与 ba。如果ab < ba,则a < b;如果ab > ba,则a > b;如果ab = ba,则a = b。比较函数的定义是本解决方案的关键。这道题其实就是希望我们能找到一个排序规则,根据这个规则排出来的数组能排成一个最小的数字。;
命题:最小数字满足上述规则。(最小数字满足上述规则—>按照上述规则可以找到最小数字,这显然不是充要条件,但按照上述规则得到的结果只有一个,并且最小数字也只有一个,那么如果按照上述规则找到一个数字,它必然为最小数字。所以这是一个充要条件)
证明(反证法):
参考资料:【百度面试题】把数组排成最小的数
首先:两个数字m和n能拼接成mn和nm,如果mn<nm,那m应该在前;如果nm<mn,那么n应该在前。因此,我们得到的排序规则如下:
- 若mn>nm,则m大于n
- 若mn<nm,则m小于n
- 若mn=nm,则m等于n
假设存在最小数字不满足上述规则,用数学语言描述则为:假设排成的最小数字为xxxxxx,并且至少存在一对字符串满足这个关系:b <a(即:ba < ab,即b和a的相对位置应该是b在前),但是在组成的数字中a排在b前面。根据a和b出现的位置,分三种情况考虑:
(1)xxxxab,用ba代替ab可以得到xxxxba,这个数字是小于xxxxab,说明不满足上述规则的情况:xxxxab不是最小数字,与假设矛盾(假设中它是最小数字,如今找到了更小的数字)。因此排成的最小数字中,不存在上述假设的关系。
(2)abxxxx,用ba代替ab可以得到baxxxx,这个数字是小于abxxxx,与假设矛盾。因此排成的最小数字中,不存在上述假设的关系。
(3)axxxxb,这一步证明麻烦了一点。可以将中间部分看成一个整体ayb,则有ay < ya(首先ayb是最小数字,把a当成上面说到的m,y当成n,则a和y必定满足:ay<ya,否则yab<ayb,即ayb不是最小数字了),yb < by成立。将ay和by表示成10进制数字形式,则有下述关系式,这里a,y,b的位数分别为n,m,k。
关系1: ay < ya => a 10^m + y < y 10^n + a => a 10^m - a < y 10^n - y => a( 10^m - 1)/( 10^n - 1) < y
关系2: yb < by => y 10^k + b < b 10^m + y => y 10^k - y < b 10^m - b => y < b( 10^m -1)/( 10^k -1)
由关系1和关系2可以得到关系3: a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1) => a/( 10^n - 1)< b/( 10^k -1) 传递性=> a10^k - a < b 10^n - b =>a10^k + b < b 10^n + a (其实这个式子描述的意思是:ab
这与假设a > b矛盾。因此因此排成的最小数字中,不存在上述假设的关系。
综上所述,得出假设不成立。从而得出结论:对于排成的最小数字,不存在满足下述关系的一对字符串:a > b,但是在组成的数字中a出现在b的前面。即:最小数字必定满足上述规则。
补充内容:Java库中的排序函数
1 | #python |
1 | //java |
35、数组中的逆序对
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
输入描述:
题目保证输入的数组中没有的相同的数字数据范围:
- 对于%50的数据,size<=10^4
- 对于%75的数据,size<=10^5
- 对于%100的数据,size<=210^5
*解题思路:
归并排序的过程刚好可以统计出逆序对的个数。关键在于写出归并排序的非递归过程。由于对于归并排序并不熟悉(熟悉的排序方法只有选择和冒泡,能随手就写的也只是选择排序法的原始版本),所以此处以深刻理解代码为主,达到默写水平。
注意问题:
1.res = res%1000000007;语句的位置,必须是每次更新完res之后就取模,否则会有50%的用例通不过;
2.res累加的数应该是:mid - i + 1,这个需要细细体会;
3.通过该题应对归并排序的程序熟练掌握;
补充知识点:归并排序(分治、递归)、
1 | #python |
1 | //java |
37、数字在排序数组中出现的
题目描述:
统计一个数字在排序数组中出现的次数。例如,输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于数字3在该数组中出现了4次,所以函数返回4。
解题思路:巧用二分搜索。找到第一个k和最后一个k的位置。
既然输入的数组是有序的,所以我们就能很自然的想到用二分查找算法。以题目中给的数组为例,一个比较自然的想法是用二分查找先找到一个3,由于要计算的是输出的次数,所以需要在找到的这个3的左右两边分别再进行顺序扫描,进而得到3的个数,这样最坏的情况下时间复杂度仍然是O(n),和直接顺序扫描的效率相同。
因此,需要考虑怎样更好的利用二分查找算法,由于数组有序,如果知道了第一个k出现的位置和最后一个k出现的位置,那么我们就可以直接算出有多少个k。因此将思路转化为通过二分查找求第一个和最后一个k出现的位置。
以第一个k出现的位置为例,利用二分查找算法可以直接对数组进行二分,而每次总是拿中间的数字和k做比较,如果中间的数字大于k,那么第一个k只有可能出现在左边,下一次直接在数组左半段继续进行二分查找;如果中间的数字小于k,则第一个k只有可能出现在右边,则在右半段再查找;如果中间的数字等于k,我们先判断它前面的一个数字是不是k,如果不是,那么这个中间的数字就是第一个出现的位置,反之,如果中间数字前面的数字是k,那么第一个k仍然在前半段,继续查找。
同理,找最后一个k出现的位置方法类似,可以使用两个函数分别获得。
注意问题:
1.注意处理特殊情况:
(1).{3,3,3,3} k=3;
(2).{} k=3;
(3).{1,2,4,5} k=3/0/6;
2.注意找完left之后,low、mid、high要进行初始化。
1 | #python |
1 | //java |
40、数组中只出现一次的数字
题目描述:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1)。
注意问题:
1.index必须是从0开始:res本身的最后一位就是1,则不需要移动就找到了。index<32:java的int类型有4个字节,最高位为符号位,右移整数高位补0,负数高位补1。
2.返回类型为viod的方法也可以通过return ;
语句结束方法的执行;
3.把res初始化为0是因为:0^a=a
;
4.判断一个整数二进制的最后一位是否为1的办法:(res>>index & 1)==1
。1的二进制为:00000000 00000000 00000000 00000001,与res进行”按位与(&)“操作,就可以判断最后一位是否为1(高位的0可以把res的高位全部清除,最后的结果是0还是1只取决于res的最后一位,妙哉);
5.按照array[i]>>index & 1
是0还是1将数组分成两部分,分别异或。此处分成两部分并不开辟新的空间存储,而是采取区分一个计算一个的方法。所以空间复杂度依然是O(1);
补充知识点:Java的位移、异或操作、原码、反码、补码
1 | #python |
1 | //java |
50、数组中的重复数字
题目描述:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
解题思路:巧用桶排序。
注意问题:
1.第二个循环用while。因为无法确定需要换多少次才能换到numbers[i]==i
;
2.技巧性比较强,需要细细品味,反复思考,力求达到选择排序法的熟悉度。
补充知识点:桶排序
1 | #python |
1 | //java |
51、构建乘积数组
题目描述:
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1]。
其中B中的元素B[i]=A[0] * A[1]... * A[i-1] * A[i+1]... * A[n-1]
。不能使用除法。
解题思路:典型的动态规划;
注意问题:
1.时间复杂度分析:原始想法:对于每一个B[i](n-1),计算其值(n-1),时间复杂度为O(n^2);动态规划:一个for循环用三次(数组C、D和B),时间复杂度为O(n)。
2.java在类的方法中创建的数组可以作为返回值。C语言也可以。例如:
1 |
|
补充知识点:动态规划
1 | #python |
1 | //java |