---

直接刷題鏈接直達

• 把一個數組排成最大的數
  • 劍指 Offer 45. 把數組排成最小的數
  • 面試官說需要 通過 補位 思想（普通的compare再sort并不滿意，但補位思想似乎不適用于有重復元素的情況）
• 如何給一個很大的無序數組去重
  • 26. 刪除排序數組中的重復項（給排序數組去重）
• 求兩個排序數組的中位數
  • 要求時間復雜度 O(log(m+n))
  • 二分查找，遞歸求整個數組中第K大的元素，完整代碼需要仔細考慮多種邊界條件
  • 4.尋找兩個有序數組的中位數
• 求一個循環遞增數組的最小值
  • 153. 尋找旋轉排序數組中的最小值 （無重復元素，二分，總有一半有序，注意邊界）
  • 154. 尋找旋轉排序數組中的最小值 II （有重復元素，需要解除相等時的死循環）
• 數組中的逆序對
  • 歸并排序 && 遞歸的應用
  • 引入輔助數組臨時存放排序好的數據
  • 歸并時指向兩個指針末尾，逐次向前并統計
  • 面試題51. 數組中的逆序對
• 如何找到一個無序數組的中位數
  • 295. 數據流的中位數 （建立兩個堆，最大堆&最小堆，復雜度分析）
  • 找出一個無序數組的中位數 （快排，縮小Partition區域 / 取一半元素建堆）
• 鏈表排序
  • 需要 nlog(n) 時間復雜度和常數級空間復雜度
  • 歸并排序的應用（Bottom Up）
  • 找到中點，斷開鏈表（通過快慢兩個指針）
  • 交替雙指針合并
  • 148. 排序鏈表
• 手寫主流排序算法 & 各種算法的復雜度/穩定性分析
  • 常見問題
    • 手寫快排 / 堆排
    • 快排的復雜度分析（最好/最壞/平均）
    • 堆排中建堆的時間復雜度分析 --> O(n)
      • 堆排序中建堆過程時間復雜度O(n)怎么來的？
      • 為什么建堆的時間復雜度是O(n)？
    • 歸并排序的 Top-Down & Bottom-up 策略
    • 不同排序的穩定性分析
    • 冒泡排序的優化策略（華為）
      • 設置flag位，一輪未交換數據即已完成排序，提前結束
      • 記住本輪最后一次交換發生的位置lastExchange，下次內層循環到此終止即可
  • 排序算法穩定性
  • 排序算法可視化
  • 快排 Wiki / 堆排 Wiki / 歸并排序 Wiki
  • 堆排序(Heapsort) （特別好的講解）
  • 冒泡排序算法及其兩種優化
• （Top K 問題）給定一個無符號，包含10億個數的數組，如何取出前100大的數
  • 答題思路
    • 首先詢問資源 --> 內存 / 核數 / 單機or多機，如可用多機 --> MapReduce思想
    • 堆排 O(nlogk)，可以單機處理海量數據（在內存受限情況下），如果k較小，趨近于 O(n)
      • 建立一個容量為k的大/小頂堆
      • n個元素逐一比較，O(logk) 完成刪除和插入操作
    • 全局排序， O(nlogn) （數據量較小時才可行）
    • 冒泡（k個），O(kn)
    • 快排劃分 O(n)， 每次遞歸處理一側的數據，理論上可以理解為每次折半，缺點 --> 存在內存不夠的問題，因為需要一次讀入所有數據
  • 算法必學：經典的 Top K 問題（基本思路篇）
  • 海量數據處理 - 10億個數中找出最大的10000個數（top K問題） （各種資源場景分析，面試前可參考）
  • 最小的K個數（代碼實現，首選堆排）
• Java自帶的 sort() 方法是如何實現的
  • Array.sort() / Collections.sort()
  • DualPivotQuicksort（雙軸快速排序）
  • Arrays.sort和Collections.sort實現原理解析
  • Collections.sort()和Arrays.sort()排序算法選擇
• 寫一個快速劃分數據集的算法，要求測試集用新數據，訓練集用老數據
  • 數據格式為 Record（id, timestamp）
  • 函數簽名為 division(ArrayList dataset, double ratio)， ratio為(0,1)的劃分比例
  • 要求復雜度為O(n)
• 從一大段文本中找出TOP K 的高頻詞匯
  • System Design Interview - Top K Problem (Heavy Hitters) （系統設計角度思考本題，如何權衡性能和效率，較為高階）
  • 347. 前K 個高頻元素 （數字頻次代碼實現，建堆，時間復雜度為nlog(k)）
  • 692. 前K個高頻單詞 （詞匯頻次代碼實現，思路一致）

---

把數組排成最小的數

題目：闖關游戲需要破解一組密碼，闖關組給出的有關密碼的線索是：

• 一個擁有密碼所有元素的非負整數數組 password
• 密碼是 password 中所有元素拼接后得到的最小的一個數

class Solution {public String crackPassword(int[] password) {String[] strs = new String[password.length];for (int i=0; i < password.length; i++) {strs[i] = password[i] + "";}Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));StringBuilder sb = new StringBuilder();for (int i=0; i < password.length; i++) {sb.append(strs[i]);}return sb.isEmpty() ? "0":sb.toString();}
}

---

刪除有序數組中的重復項

給你一個 非嚴格遞增排列 的數組 nums ，請你 原地 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除后數組的新長度。元素的 相對順序 應該保持 一致 。然后返回 nums 中唯一元素的個數。

考慮 nums 的唯一元素的數量為 k ，你需要做以下事情確保你的題解可以被通過：

• 更改數組 nums ，使 nums 的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現的順序排列。nums 的其余元素與 nums 的大小不重要。
• 返回 k 。

class Solution {public int removeDuplicates(int[] nums) {if (nums.length == 0) return 0;int k = 0;for (int i = 1; i < nums.length; i++) {if (nums[i] != nums[k]) {nums[++k] = nums[i];}}return k+1;}
}

---

求兩個排序數組的中位數

題目：
給定兩個大小分別為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并返回這兩個正序數組的 中位數 。

• 算法的時間復雜度應該為 O(log (m+n)) 。

解法：
這道題的關鍵是 二分查找+數組切割，核心思路是 在較短數組上二分查找，然后通過數學推導找到合適的中位數。

• 設定兩個數組 nums1 和 nums2，保證 nums1 總是最短的數組（這樣可以減少二分查找的搜索范圍）。

• 對短數組進行二分查找，設 nums1 的長度為 m，nums2 的長度為 n，則我們希望找到一個分割點 i（在 nums1 中），同時 j = (m + n + 1) / 2 - i（在 nums2 中）。

• 確保分割點左側的所有元素 ≤ 右側的所有元素：

• nums1[i-1] <= nums2[j]

• nums2[j-1] <= nums1[i]

• 確定中位數：

• 如果 m + n 是 奇數，中位數是左半部分的最大值 max(nums1[i-1], nums2[j-1])。

• 如果 m + n 是 偶數，中位數是 (max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j])) / 2。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 保證 nums1 是較短的數組if (nums1.length > nums2.length) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.length, n = nums2.length;int left = 0, right = m;int medianPos = (m + n + 1) / 2; // 中位數的位置while (left <= right) {int i = left + (right - left) / 2;  // nums1的分割點int j = medianPos - i;             // nums2的分割點int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {// 找到合適的分割點if ((m + n) % 2 == 0) {return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;} else {return Math.max(nums1LeftMax, nums2LeftMax);}} else if (nums1LeftMax > nums2RightMin) {// 需要向左移動right = i - 1;} else {// 需要向右移動left = i + 1;}}throw new IllegalArgumentException("輸入的數組不符合條件");
}

---

求一個循環遞增數組的最小值

題目： 已知一個長度為 n 的數組，預先按照升序排列，經由 1 到 n 次 旋轉 后，得到輸入數組。例如，原數組 nums = [0,1,2,4,5,6,7] 在變化后可能得到：

• 若旋轉 4 次，則可以得到 [4,5,6,7,0,1,2]
• 若旋轉 7 次，則可以得到 [0,1,2,4,5,6,7]

class Solution {public int findMin(int[] nums) {if (nums == null || nums.length == 0) {throw new IllegalArgumentException("數組不能為空");}int left = 0, right = nums.length - 1;while (left < right) { // 這里是 left < right，而不是 left <= rightint mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {  // 最小值一定在 mid 右側left = mid + 1;} else {// 最小值可能在 mid 或左側right = mid;}}return nums[left]; // 最終 left == right，返回最小值}
}

題目 ： 已知一個長度為 n 的數組，預先按照升序排列，經由 1 到 n 次 旋轉 后，得到輸入數組。例如，原數組 nums = [0,1,4,4,5,6,7] 在變化后可能得到：

• 若旋轉 4 次，則可以得到 [4,5,6,7,0,1,4]
• 若旋轉 7 次，則可以得到 [0,1,4,4,5,6,7]

class Solution {public int findMin(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[right]) {left = mid + 1;}else if (nums[mid] < nums[right]) {right = mid;}else {// nums[mid] == nums[right]right--;}}return nums[left];}
}

---

數組中的逆序對

題目 ：在股票交易中，如果前一天的股價高于后一天的股價，則可以認為存在一個「交易逆序對」。請設計一個程序，輸入一段時間內的股票交易記錄 record，返回其中存在的「交易逆序對」總數。

class Solution {public int reversePairs(int[] record) {if (record == null || record.length < 2) return 0;mergeSort(record, 0, record.length - 1);return count;}public void mergeSort(int[] record, int left, int right) {if (left >= right) return;int mid = left + (right-left)/2;mergeSort(record, left, mid);mergeSort(record, mid+1, right);// 合并merge(record, left, mid, right);}int count = 0;public void merge(int[] record, int left, int mid, int right) {int[] temp = new int[right - left +1];int i = left, j = mid+1;int k = 0;while (i <= mid && j <= right) {if (record[i] <= record[j]) {temp[k++] = record[i++];}else {//當左邊數組的大與右邊數組的元素時，就對當前元素以及后面的元素的個數進行統計，//此時這個數就是，逆序數//定義一個計數器，記下每次合并中存在的逆序數。count += mid - i + 1;temp[k++] = record[j++];}}while (i <= mid) temp[k++] = record[i++];while (j <= right) temp[k++] = record[j++];//將新數組中的元素，覆蓋nums舊數組中的元素。//此時數組的元素已經是有序的for(int t =0; t< temp.length;t++){record[left+t] = temp[t];}}
}

---

如何找到一個無序數組的中位數

中位數是有序整數列表中的中間值。如果列表的大小是偶數，則沒有中間值，中位數是兩個中間值的平均值。

例如 arr = [2,3,4] 的中位數是 3 。
例如 arr = [2,3] 的中位數是 (2 + 3) / 2 = 2.5 。
實現 MedianFinder 類:

MedianFinder() 初始化 MedianFinder 對象。

void addNum(int num) 將數據流中的整數 num 添加到數據結構中。

double findMedian() 返回到目前為止所有元素的中位數。與實際答案相差 10-5 以內的答案將被接受。

class MedianFinder {PriorityQueue<Integer> left;PriorityQueue<Integer> right;public MedianFinder() {left = new PriorityQueue<>((a,b)->b-a); // 最大堆right = new PriorityQueue<>(); // 最小堆}public void addNum(int num) {if (left.size() == right.size()) {right.offer(num);left.offer(right.poll());} else {left.offer(num);right.offer(left.poll());}}public double findMedian() {if (left.size() > right.size()) {return left.peek();}return (left.peek() + right.peek()) / 2.0;}
}

---

鏈表排序

class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;// 歸并排序ListNode slow = head;ListNode fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode newHead = slow.next;slow.next = null;ListNode left = sortList(head);ListNode right = sortList(newHead);ListNode dm = new ListNode(0);ListNode curr = dm;while (left != null && right != null) {if (left.val < right.val) {curr.next = left;left = left.next;curr = curr.next; }else {curr.next = right;right = right.next;curr = curr.next;}}if (left != null) {curr.next = left;}if (right != null) {curr.next = right;}return dm.next;}
}

---

從一大段文本中找出TOP K 的高頻詞匯

題目： 給你一個整數數組 nums 和一個整數 k ，請你返回其中出現頻率前 k 高的元素。你可以按 任意順序 返回答案。

class Solution {public int[] topKFrequent(int[] nums, int k) {PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {map.put(nums[i], map.getOrDefault(nums[i], 0)+1);}for (int key : map.keySet()) {if (pq.size() < k) {pq.offer(new int[]{key, map.get(key)});}else {if (pq.peek()[1] < map.get(key)) {pq.poll();pq.offer(new int[]{key, map.get(key)});}}}int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = pq.poll()[0];}return ans;}
}

題目： 給定一個單詞列表 words 和一個整數 k ，返回前 k 個出現次數最多的單詞。

返回的答案應該按單詞出現頻率由高到低排序。如果不同的單詞有相同出現頻率， 按字典順序 排序。

class Solution {public List<String> topKFrequent(String[] words, int k) {Map<String, Integer> map = new HashMap<>();for (int i = 0; i < words.length; i++) {map.put(words[i], map.getOrDefault(words[i], 0)+1);}PriorityQueue<String> pq = new PriorityQueue<>((a,b)->{//如果不同的單詞有相同出現頻率， 按字典順序 排序if (map.get(a) == map.get(b)) {return b.compareTo(a);}return map.get(a) - map.get(b);});for (String s:map.keySet()) {pq.offer(s);if (pq.size() > k) {pq.poll();}}String[] ans = new String[k];for (int i = k-1; i >= 0; i--) {ans[i] = pq.poll();}return Arrays.asList(ans);}
}

---