数据结构·面试·数组高频题·中位数问题第K大问题等
- 2020 年 2 月 17 日
- 筆記
思路提要
- 求两个有序数组的中位数
- 奇数个数的中位数只有1个， 偶数个数的中位数可能有两个。 在有些题目中，把[2 3 5 7] 的中位数认为是4。 在数据量Ｌ已知情况下，将求中位数转化为求第k小问题，本质上是求第k小问题。
- 暴力解法： O（（m+n）/2） 每次取A和B头部最小的一个数，直到取到第 L/2 + 1 个数（当L为奇数时）。
- 【3】求两个等长、有序数组的中位数（二分法）
- 数组长度为len，数据个数2*len，中位数为第len、len+1大的数。
- 暴力法：排好序后找。
- 二分法：忘了，直接查答案吧。
- 【4】求两个不等长、有序数组a和b的中位数（排除法 ）
- 最优解 O(log (m+n)) 。中位数为第k小数。限定数组为升序。 如果a[k/2] == b[k/2], 那么中位数是a[k/2]或者a[k/2]比中位数小，a、b的前k/2的数都要排除, 更新 k = k – k/2 -k/2；如果a[k/2] < b[k/2], 那么a[k/2]最多只可能是第 （k/2）+ （k/2 – 1）= k -1 小的数，所以a的前k/2个数都可以删除， 更新 k = k – k/2 。 且 b[] a的前k/2个数中一定不包含第k大数，否则不断删除个 k/2个数，然后 k = k/2。
- 详细讲解.求两个不等长、有序数组a和b的中位数的最优解（排除法 ）
- （leetcode）【3】旋转数组求最小值 （二分法）
- 【3】旋转数组求查找某个值是否存在（先用二分法logn找到最小值的index，判断出目标值在leftpart还是rightpart，然后用二分法找到目标值。 不知道是不是最优解，但最优解最多是logm ）
- 【4*】【剑指offer原题】每行从左到右，每列从上到下严格递增（递减）的二维数组中，判断某个数是否存在.
- 暴力法：先跟每一行的最后一个数比较确定其在哪一行（O(n)），再在确定的行中二分查找O(lgm)最优解 O(n)， 排除法，见后文。
- 最优解：
- （这一段说得好乱）每一行数或每一列数都算作一个序列，右上角（或左下角）是两个序列的头(或尾)，且这两个序列连起来是一个严格递增（或递减）的大序列，角落数在这个递增或递减的大序列里，目标数如果不等于角落里的数，那么根据目标数和角落数的相对大小一定可以确定其不在两个序列中的一个序列，从而排除这个序列。
- 不断做排除，直到角落数等于目标数。 O(n)
- 例题：https://blog.csdn.net/wzwdcld/article/details/81606960
- *【3*】【我面阿里是遇到的】每行从左到右，每列从上到下递增，且下一行全部大于上一行的二维数组中，判断某个数是否存在.
- 暴力：先跟每一行的最后一个数比较确定其在哪一行（O(n)），再在确定的行中二分查找O(lgm)
- 排除法：O（n）
- 最优解：将输入的二维数组a[i][j]和一维数组b[k]间做单射， b[k] = a[k/m][k%m], 对长度为mn的b数组做二分查找，O(lg(mn))
- 【3*】数组中出现次数超过一半的数字 O(n)
- ret记录出现次数最多的数，count为其出现的相对次数。 遍历，当前数字和ret相同，则count++，否则count–，如果count变为0，ret的值取下一个数字。
- 无序数组求最大值、第二大值、第三大值
- 直接建堆 O(lgn),堆顶就是最大值
- 【3*】求无序数组中第 k 大的数或中位数（分数组长度奇数和偶数）（拓展：最大的 k 个数）
- 用数组前k个数建立大小为k的最小堆，堆顶元素始终为堆中的第K大数，普通数组到堆数组建堆过程O(k).
- 之后的n-k个数逐一和堆顶比较，如果比堆顶大就替换堆顶，然后堆顶元素下沉直到重新成为堆( O(logk) ), 整体 （n-k)*O(logk)
- 整体时间复杂度O(nlogk)， 额外空间 O(k)
- 额外空间 O(n)的解法：
- 建立最大堆 O（N）
- 找数 O(klgN)，即堆数组转化为有序数组。 不断的从大根堆中删除堆顶元素放到数组末尾，原堆部分重新调整为堆(O(lgN)),一共进行K次，数组最后k个数就是一个长度为k的降序数组。
- 【3*】有序数组中某个数字出现的次数（提示：利用二分搜索）
