十道考研数学经典算法笔试真题及解析

　　今天小编为大家分享的是腾讯算法岗敲门砖，十道经典算法笔试真题及解析，希望通过这篇文章的学习对你们有所帮助，下面跟随小编一起学习吧。
　　给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
　　一、层 for 循环从索引 0 到倒数第二个索引拿到每个数组元素，第二个 for 循环遍历上一层 for 循环拿到的元素的后面的所有元素。
　　题目4：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序， 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
　　对于一般数组，普通遍历方式即可判断数组中是否含有该元素。对于二维数组，两层 for 循环即可，时间复杂读为 o (n*n);
　　对于本题，二维数组行按升序排列，列也按升序排列，我们可以使用一点小技巧：从数组的左下角开始遍历数组，能更有效率的解决问题。
　　题目5：把一个数组开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的小元素。例如数组 为 的一个旋转，该数组的小值为 1。注意：给出的所有元素都大于 0，若数组大小为 0，请返回 0。
　　1. 遍历整个数组，找到小值，通过比较找到小值，该方法太蛮力。
　　2. 根据数组是非减排序数组旋转得来，可以在遍历的时候优化一下，遍历直到 a [i]>a [i 1]; 此时 a [i 1] 就是小值，输出即可。
　　3. 思路 2 好情况遍历一次，差情况遍历 n 次，我想到一种思路：
　　假设旋转后的数组为 array []，其大索引为 end，小值为 min，将数组按 min 的左右分为左区和右区，
　　其中左区满足两个条件：
　　array [i] > array [end] 了该元素在左边
　　array [i]
　　其中右区满足两个条件：
　　array [i]
　　array [i] >= array [i - 1] 了该元素不是右区的边界值
　　因此除了上述情况就只剩下左区边界和右区边界了，就很好得到小值了。
　　题目6：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O (log (m n))。你可以假设 nums1 和 nums2 不会同时为空。
　　示例 1:
　　示例 2:
　　1、因为是两个有序数组，所以需要两个割点 C1，C2。若将两个数组 (都是升序排序的数组) 分别在一个割点处分为两半，那么 L1（数组前半部分的右边的元素) 一定是小于 R1 (数组后半部分左边的元素)，同理 L2
　　因为要找两个有序数组的中位数（为了方便奇偶性的区分，我们将两个数组分别虚拟设置为奇数，所以两个数组看为一个数组的时候，元素个数为偶数，中位数 =(m1 m2)/2，此时只要找到 m1,m2 中位数便可以求出），若割点刚好处于中间，此时只需要找到当 L1
　　同理当 R1>L2,R2>L1 时候，比较 R1 和 R2 的数值，找出小的（因为右半部分从左到右依次增大，那么找出靠近左边的那个数 m2）。此时 (m1 m2)/2 便是要求的中位数。
　　2、首先一个数组要求中位数，必须是排序好，而且要分奇偶，才能求出中位数。现在是两个数组，奇偶性都在不确定，所以原博主很明智地将数组进行了处理，通过虚拟地加入 #符号，使得数组恒为奇。（例如：1，2，48，90 虚拟加 #符号后变为：#1#2#48#90#），此处的处理是通过公示：2n 1 始终是奇数而来的。代码中并没有实际加入符号 #，只是将数组的长度进行了 2n 1 的翻倍。
　　3、所以只要找到处于中间的那个割点 K，并找到 K 左右的两个数值，就可以求出中位数。对于单个有序数组，K 的位置就是在数组长度一半的位置（当然要分奇偶）。偶数的话就是 K 左右的两个数值相加除以 2，奇数的话，也就是 K 所在的位置。那么对于两个有序数组的话，如果 left1,left2 (两个数组的左半部分) 的元素个数相加等于 K 的时候，比较 L1，L2 找出大的那个数值，那个数值就是 K 左边的值，同理，K 右边的值就是 R1，R2 中小的那个。若假设数组 1 的割点为 C1，数组 2 的隔点为 C2，那么当 C1 C2 = K 的时候，就可以进行比较。

　　4、比较的时候，如果 L1 > R2 的时候，就需要将 C1 往左移动（左边数值更小），将 C2 往右移动（右边数值更大），直到满足 L1
　　同理，如果 L2 > R1 的时候，就需要将 C2 往左移动，C1 往右边移动，直到满足 L2
　　此处需要考虑越界的问题：
　　若当 C1=0，移动到了左边或者 C2 移动到了右边，都还不满足 L1 数组 2，此时中位数在数组 2 中，若当 C2=0，移动到了左边或者 C1 移动到了右边，还不满足 L2
　　5、假设数组 1 长度为 n, 数组 2 长度为 m, 并且 n
　　将数组长度进行虚处理，然后再把两个数组看作是数组 A。
　　此时长度为（2m 1) (2n 1)=2m 2n 2 此时从中间隔开，k = (2m 2n 2)/2=(m n 1), 因为数组 A 是从下标 0 开始计数的，所以在程序中 K 实际等于 (m n). 知道 K 值之后，C1，C2 任意知道其中一个，便可以确定另外一个，此处对长度较小的数组进行二分，所以确定 C1 后再确定 C2， C2 = k-C1=m n-C1. 此时我们将数组进行了虚拟的加 #，所以要确定原来数组元素的真正位置，就包含一个映射关系。L1 =(C1-1)/2 L2=(C2-1)/2 R1=(C1/2) R2=(C2/2)