头条 一面挂 😂😂😂

      如果这个数是有范围的比如是int的范围，那就可以二分数的范围来查找。      1.那么可以假设用 （int最大值+int最小值）/2,作为假设中位数mid。      2.对于k个数组，均去查找mid所对应的位置，然后计算所有数组中比mid小和比mid大的数的个数lcont,rcount，因为是有序的，这个过程只要 klogn （n为数组长度）。      3.如果lcount==rcount ，那么mid就是真正的中位数       4.否则继续二分范围，比如lcount大，就让mid往左二分。 总的时间复杂度应该是log（数的范围）*k*logn  。log（数的范围） 一般不大，int的话就32

/** * Created by tlh on 2017/5/17. * 求两个排序数组合并后的中位数 * 设数组A和B，长度分别为m和n, 要求时间复杂度为O(log(m+n))。 * 用二分查找的思想，求合并后数组的第k个数。每次二分的过程都要设法舍弃掉数组的一部分，从而达到收敛缩小查找范围的效果。 * 从数组A和B分别取第k/2个数，当A[k/2-1] < B[k/2-1],则A的前k/2个元素必定在合并后的数组的前k个元素内，舍弃这A的前k/2个元素。 * 否则，舍弃B中前k/2个数。 * 接下来，递归在剩下的(m+n-k/2)的元素中找第(k-k/2)元素。 * https://www.jiuzhang.com/qa/1768/ */ public class MedianOfTwoSortedArrays { // 找到第K个元素 private int findKth(int[] A, int iA, int jA, int[] B, int iB, int jB, int k) { int m = jA - iA + 1; // 数组A的长度 int n = jB - iB + 1; // 数组B的长度 if (n < m) return findKth(B, iB, jB, A, iA, jA, k); // 保证数组A长度比数组B长度小 if (m == 0) return B[k - 1]; // 当较小的数组跑完了，返回数组B的第k个 if (k == 1) return Math.min(A[iA], B[iB]); // 返回第1个数 // 将k分成两部分 int lenA = Math.min(k / 2, m); // 取数组A的前lenA个元素 int lenB = k - lenA; // 取数组B的前lenB个元素 int pa = iA + lenA - 1; // 数组A的第lenA个元素 int pb = iB + lenB - 1; // 数组B的第lenB个元素 // 判断A[pa]和B[pb]的大小 if (A[pa] < B[pb]) return findKth(A, pa + 1, jA, B, iB, jB, k - lenA); // 舍弃数组A的前lenA个元素 else if (A[pa] > B[pb]) return findKth(A, iA, jA, B, pb + 1, jB, k - lenB); // 舍弃数组B的lenB个元素 else return A[pa]; // A[pa]或B[pb]就是对应的第k个数 } public float getMedian(int[] A, int[] B) { int totalLen = A.length + B.length; if ((totalLen & 1) == 1) { // 总数组长度为奇数 return findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2); } else { // 总数组长度为偶数 return (findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2) + findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2 + 1)) / 2.0f; } }

第二题百度考了，不过是个简单版，给俩有序数组找中位数，要求复杂度log（数组和的长度）

楼主面的什么岗位？

都已经有序了？还求什么中位数

面试官是个女的？

感觉你第一题答出来，第二题把k=2说清楚，应该没问题

第二个题目可以 维护两个堆来找中位数。

我是来看大神怎么解的~

为啥头条面试官都是女的

第一题的做法是： 将所有数字都在最后补充0，直到到位数相同，即位数不够的一直乘10，然后从小到大排序，第m个数字删去最后补充的0就是答案。 时间复杂度大约是n*logn，补0是复杂度为19*n，logn和19相差不大。

第一题，是这个题目？http://blog.csdn.net/fool _ran/article/details/40479059

第二道题，二分，

关于第一题,   是不是可以用堆排序?     定义某种比较函数cmp, 使得可以让11>101.     维护一个大小为m的大顶堆, 取前m个元素组成大顶堆, 遍历剩下的n-m个元素, 对于新的元素, 如果小于堆顶元素, 就替换堆顶元素,并调整堆, 否则就跳过该元素.继续比较下一个新的元素. 直到所有元素遍历完, 返回堆顶元素. 这样做的复杂度为O(nlog(m)). 但这种做法不适用于m很大的情况.

初步思考了一下，说一下自己的想法，如有误，轻喷... 对于第一题，字典序也是一种全序，这样的话使用partition的思路应该也可以O(log(n))，需要自己定义比较函数 对于第二题，应该是和2个数组的情况类似，相当于判断k个数组的第rank / k 个元素，找其中最小的淘汰元素。感觉实现起来也挺复杂，复杂度的话是在O(klogn)吧，不太确定 之前还想了使用堆的方法，就是使用一个最小堆存储数组首地址（指针），键值就是首元素值，然后每次取堆顶指针对应元素，递增指针，这样就改变了键值，调整堆，然后重复过程n/2次找到中位数 复杂度是O(klogk + n/2 * logk)，只是比nk稍微好一点。。。。。。