刷題路線參考： https://github.com/chefyuan/algorithm-base
大家好，我是拿輸出部落格督促自己刷題的老三，前面學習了十大排序：
萬字長文|十大基本排序，一次搞定！，接下來我們看看力扣上有沒有什麼能拿排序解決的題目吧！
排序基礎
簡單了解一下基本的排序——
基本排序分類：
基本排序性能：
| 排序方法 | 時間複雜度（平均） | 時間複雜度（最壞） | 時間複雜度（最好） | 空間複雜度 | 穩定性 |
| 冒泡排序 | O(n²) | O(n) | O(1) | 穩定 | |
| 選擇排序 | 不穩定 | ||||
| 插入排序 | |||||
| 希爾排序 | O(n^(1.3-2)) | ||||
| 歸并排序 | O(nlogn) | ||||
| 快速排序 | |||||
| 堆排序 | |||||
| 計數排序 | O(n+k) | ||||
| 桶排序 | |||||
| 基數排序 | O(n*k) |
更具體的可以檢視：
好了，開始我們愉快的刷題之旅吧！
刷題現場
LeetCode912. 排序數組
☕ 題目：912. 排序數組 (https://leetcode-cn.com/problems/sort-an-array/)
❓ 難度：中等
📕 描述：給你一個整數數組
nums
，請你将該數組升序排列。
示例 1：
輸入：nums = [5,2,3,1]
輸出：[1,2,3,5] 示例 2：
輸入：nums = [5,1,1,2,0,0]
輸出：[0,0,1,1,2,5] 💡 思路：
這道題如果用api，一行就搞定了——
Arrays.sort(nums)
，那面試官的反應多半是，門在那邊，慢走不送。
是以，毫無疑問，我們要手撕排序了。
如果對排序算法不太熟，可以上一個
冒泡排序
，但是這個明顯隻能說中規中矩，是以，我們選擇：
手撕快排
關于快排，就不多講。
直接上代碼：
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort(int[] nums,int left, int right){
//結束條件
if(left>=right){
return;
}
//分區
int partitionIndex=partition(nums,left,right);
//遞歸左分區
quickSort(nums,left,partitionIndex-1);
//遞歸右分區
quickSort(nums,partitionIndex+1,right);
}
public int partition(int[] nums,int left,int right){
//基準值
int pivot=nums[left];
//mark标記下标
int mark=left;
for(int i=left+1;i<=right;i++){
if(nums[i]<pivot){
//小于基準值，則mark後移，并交換位置
mark++;
int temp=nums[mark];
nums[mark]=nums[i];
nums[i]=temp;
}
}
//把基準值放到mark的位置
nums[left]=nums[mark];
nums[mark]=pivot;
return mark;
}
} - 🚗 時間複雜度：快排時間複雜度O(nlogn)
有時間的可以把十大排序都在這道題練上一練。
LeetCode347. 前 K 個高頻元素
☕ 題目：347. 前 K 個高頻元素(https://leetcode-cn.com/problems/top-k-frequent-elements/)
📕 描述：
給你一個整數數組
nums
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2] 示例 2:
輸入: nums = [1], k = 1
輸出: [1] 提示：
1 <= nums.length <= 105
k 的取值範圍是 [1, 數組中不相同的元素的個數]
題目資料保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的 **進階：**你所設計算法的時間複雜度 必須 優于
O(n log n)
，其中
n
是數組大小。
這道題第一思路是什麼呢？
統計元素出現頻率，從大到小排序，取前k個元素。
我們想挑戰一下進階要求，時間複雜度優于O(nlogn)，是以熟悉的冒泡、快排之類的比較類排序都不可用，隻能使用非比較類的三種排序方法：計數排序、桶排序、基數排序。
這裡我們選擇HashMap+桶排序的方式。
使用HashMap存儲元素出現頻率，使用桶排序來進行排序。
代碼如下：
public int[] topKFrequent(int[] nums, int k) {
//使用HashMap存儲元素出現頻率
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
//桶
List<Integer>[] buckets = new List[nums.length + 1];
//往桶裡添加元素出現次數
for (Integer key : map.keySet()) {
//根據出現頻率決定元素入哪個桶
int count = map.get(key);
//初始化桶
if (buckets[count] == null) buckets[count] = new ArrayList<>();
//将元素存到桶中
buckets[count].add(key);
}
//結果清單
List<Integer> result = new ArrayList<>();
//取倒數k個非空桶中的元素
for (int i = buckets.length - 1; k > 0; i--) {
if (buckets[i] != null) {
//取出桶中的元素
for (Integer num : buckets[i]) {
result.add(num);
k--;
}
}
}
//将清單中的元素賦給數組
int[] res = new int[result.size()];
for (int i = 0; i < res.length; i++) {
res[i] = result.get(i);
}
return res;
} - 🚗 時間複雜度：這道題用了桶排序，時間複雜度O(n)。
劍指 Offer 45. 把數組排成最小的數
☕ 題目：劍指 Offer 45. 把數組排成最小的數 (https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/)
輸入一個非負整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個。
輸入: [10,2]
輸出: "102" 輸入: [3,30,34,5,9]
輸出: "3033459" 稍微分析一下這道題，發現這道題其實也是一道排序題。
隻要我們把數組裡的元素按照某種規則進行排序。
現在的問題就是這個排序規則是什麼呢？
因為需要拼接字元串，以[3，30]為例，“3”+“30”=“330”，“30”+“3”=“303”，330>303，那麼我們就可以說3
大于
30。
是以定義規則：
- 若拼接字元串 x+y>y+x ，則 x
大于
- 反之，若拼接字元串 x+y<y+x ，則 x
小于
規則圖如下（來源參考[2）：
那麼，這道題我們就知道怎麼寫了。
用我們自定義的排序規則從小到大排序數組。
排序方法我們選擇快排，是以這道題就是自定義排序+快排。
public String minNumber(int[] nums) {
quickSort(nums, 0, nums.length - 1);
//結果
StringBuilder sb = new StringBuilder();
for (int num : nums) {
sb.append(String.valueOf(num));
}
return sb.toString();
}
//快排
public void quickSort(int[] nums, int left, int right) {
if (left >= right) return;
int partionIndex = partion(nums, left, right);
quickSort(nums, left, partionIndex - 1);
quickSort(nums, partionIndex + 1, right);
}
public int partion(int[] nums, int left, int right) {
int pivot = nums[left];
int mark = left;
for (int i = left + 1; i <= right; i++) {
if (lessThan(nums[i], pivot)) {
mark++;
int temp = nums[mark];
nums[mark] = nums[i];
nums[i] = temp;
}
}
nums[left] = nums[mark];
nums[mark] = pivot;
return mark;
}
//自定義大小比較規則
public boolean lessThan(int x, int y) {
String sx = String.valueOf(x), sy = String.valueOf(y);
return (sx + sy).compareTo(sy + sx) < 0;
} 寫的比較臃腫，但比較清晰。
有一種利用内置排序來實作的寫法，不太建議：
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++){
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, (x,y) -> (x+y).compareTo(y+x));
StringBuilder ans = new StringBuilder();
for(String s : strs)
ans.append(s);
return ans.toString();
} - 🚗 時間複雜度：O(nlogn)。
有一道題：
179. 最大數和這道題基本一樣。
劍指 Offer 51. 數組中的逆序對
☕ 題目：劍指 Offer 51. 數組中的逆序對 (https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)
❓ 難度：困難
在數組中的兩個數字，如果前面一個數字大于後面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。
輸入: [7,5,6,4]
輸出: 5 💡思路：
這一道題是
困難
，有沒有被吓住？
其實這道題如果用歸并排序的思路去解決的話，就沒有想象中的那麼難。
歸并排序這裡就不講了。
解決這道題，我們隻需要在歸并排序的基礎上，加上對逆序對的統計：
歸并+逆序對統計示意圖（圖檔來源參考[3]）：
現在的關鍵點是，歸并的過程如何計算逆序對個數？
我們可以看一下，合并的時候，
l
指向左子數組2的位置，
r
指向右子數組0的位置，num[l]>nums[r]，因為子數組是有序的，是以
l
後面幾個元素也都一定大于0，是以可以得出，此時逆序對數量=mid-l+1。
class Solution {
//統計逆序對
int count = 0;
public int reversePairs(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return count;
}
//歸并排序
public void mergeSort(int[] nums, int left, int right) {
//結束
if (left >= right) return;
int mid = left + (right - left) / 2;
//左半部分
mergeSort(nums, left, mid);
//右半部分
mergeSort(nums, mid + 1, right);
//合并
merge(nums, left, mid, right);
}
//合并
public void merge(int[] arr, int left, int mid, int right) {
//臨時數組
int[] tempArr = new int[right - left + 1];
//指向左右子數組指針
int l = left, r = mid + 1;
int index = 0;
//把左右子數組較小元素放入到臨時數組
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
tempArr[index++] = arr[l++];
} else {
//增加一行，統計逆序對
count += (mid - l + 1);
tempArr[index++] = arr[r++];
}
}
//将左子數組剩餘的元素拷貝到臨時數組
while (l <= mid) {
tempArr[index++] = arr[l++];
}
//将右邊子數組剩餘的元素拷貝到臨時數組
while (r <= right) {
tempArr[index++] = arr[r++];
}
//将臨時數組的元素拷貝給原數組
for (int i = 0; i < tempArr.length; i++) {
arr[i + left] = tempArr[i];
}
}
} - 🚗 時間複雜度：歸并排序時間複雜度O(nlogn)。
LeetCode147. 對連結清單進行插入排序
對連結清單進行插入排序。
插入排序的動畫示範如上。從第一個元素開始，該連結清單可以被認為已經部分排序（用黑色表示）。
每次疊代時，從輸入資料中移除一個元素（用紅色表示），并原地将其插入到已排好序的連結清單中。
插入排序算法：
- 插入排序是疊代的，每次隻移動一個元素，直到所有元素可以形成一個有序的輸出清單。
- 每次疊代中，插入排序隻從輸入資料中移除一個待排序的元素，找到它在序列中适當的位置，并将其插入。
- 重複直到所有輸入資料插入完為止。
輸入: 4->2->1->3
輸出: 1->2->3->4 輸入: -1->5->3->4->0
輸出: -1->0->3->4->5 這道題不隻是插入排序，還涉及到連結清單的操作，關于連結清單，可以檢視：
LeetCode通關：聽說連結清單是門檻，這就擡腳跨門而入- 關于插入排序：我們需要從未排序序列裡将元素插入到排序序列的合适位置
- 關于連結清單插入：連結清單插入是插入節點前驅節點改變後繼的一個操作，為了頭插也能統一，通常我們會加一個虛拟頭節點
- 是以，綜合起來，我們需要标記有序序列和無序序列的分界點，周遊無序序列的時候，記錄前驅，當需要将無序序列插入到有序序列的時候，周遊有序序列，找到插入位置，先删除該節點，再插入
public ListNode insertionSortList(ListNode head) {
if (head == null && head.next == null) {
return head;
}
//虛拟頭節點
ListNode dummy = new ListNode(-1);
dummy.next = head;
//記錄有序序列終點
ListNode last = head;
//周遊無序序列
ListNode after = head.next;
while (after != null) {
if (last.val <= after.val) {
after = after.next;
last = last.next;
continue;
}
//周遊有序序列，查找插入位置
ListNode prev = dummy;
while (prev.next.val <= after.val) {
prev = prev.next;
}
//找到插入位置
//删除無序序列節點
last.next = after.next;
//插入有序序列
after.next = prev.next;
prev.next = after;
//繼續移動
after=last.next;
}
return dummy.next;
} - 🚗 時間複雜度：O(n²)。
總結
熟悉的順口溜總結：
簡單的事情重複做，重複的事情認真做，認真的事情有創造性地做。
我是三分惡，一個追求實力，正在努力的程式員。
、點贊
不迷路，咱們下期見！關注