數據結構·面試·數組高頻題·中位數問題第K大問題等
思路提要
- 求兩個有序數組的中位數
- 奇數個數的中位數只有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*】有序數組中某個數字出現的次數（提示：利用二分搜索）