原理:利用将两有序数组合并只需要线性时间的特性将数组分割,合并
void merge_sort(vector<int>& arr, int l, int r){
if(l>=r){
return;
}
int mid = (r+l)/2;
merge_sort(arr, l, mid);
merge_sort(arr, mid+1, r);
vector<int> l_arr(arr.begin()+l, arr.begin()+mid+1);
vector<int> r_arr(arr.begin()+mid+1, arr.begin()+r+1);
l_arr.insert(l_arr.end(), INT_MAX);
r_arr.insert(r_arr.end(), INT_MAX);
int i = 0,j = 0;
for(int k = l;k<=r; k++){
if(l_arr[i]<=r_arr[j]){
arr[k] = l_arr[i];
i++;
}
else{
arr[k] = r_arr[j];
j++;
}
}
}
传入与arr大小相同的split阵列
void merge_sort(vector<int>& arr, vector<int> split, int l, int r){
if(l>=r){
return;
}
int mid = (r+l)/2;
merge_sort(arr, split,l, mid);
merge_sort(arr, split,mid+1, r);
for(int i = l; i<r+1; ++i){
split[i] = arr[i];
}
int i = l,j = mid+1;
for(int k = l;k<=r; k++){
if(i==mid+1){
arr[k] = split[j++];
}
else if(j==r+1){
arr[k] = split[i++];
}
else if(split[j]<split[i]){
arr[k] = split[j++];
}
else{
arr[k] = split[i++];
}
}
}
21. Merge Two Sorted Lists
这题虽然不算是Merge Sort...但有用到合并的操作,所以放入例题(等等下一题会用到)
递回比较直观,可读性也高,迭代的细节写在注解
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 递回法
// if(l1==NULL)
// return l2;
// if(l2==NULL)
// return l1;
// if(l1->val < l2->val){
// l1->next = mergeTwoLists(l1->next, l2);
// return l1;
// }
// else{
// l2->next = mergeTwoLists(l2->next, l1);
// return l2;
// }
// return l1;
//迭代法
ListNode* preHead = new ListNode(-1);
ListNode* preHead_temp = preHead; // 用於保留root节点
while(l1!=NULL && l2!=NULL){
if(l1->val < l2->val){
preHead->next = l1;
l1 = l1->next;
}
else{
preHead->next = l2;
l2 = l2->next;
}
preHead = preHead->next;
}
// 最後会剩l1或是l2,将其合并进去
if(l1!=NULL){
preHead->next = l1;
}
else{
preHead->next = l2;
}
return preHead_temp->next;
}
};
148. 排序链表
如果有写过上面那一题,就会发现Merge Sort拿来排序链表很适合~~
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return head;
}
ListNode* first_right_node = cut_from_mid(head);
ListNode* right = sortList(head);
ListNode* left = sortList(first_right_node);
ListNode* res = merge(right, left);
return res;
}
//将List从中间分割成左链和右链,返回第一个右链节点
ListNode* cut_from_mid(ListNode* head){
ListNode* slow = head;
ListNode* fast = head;
ListNode* slow_f = nullptr; //走在slow後面,用於断开左右链
while(fast&&fast->next){
slow_f = slow;
fast = fast->next->next;
slow = slow->next;
}
slow_f->next = nullptr; //断开左右链
return slow; //回传右链第一个节点
}
//预设左右长度只差1 (分割时保证)
ListNode* merge(ListNode* left, ListNode* right){
ListNode* new_head = new ListNode();
ListNode* curr = new_head;
while(left&&right){
if(left->val < right->val){
curr->next = left;
left = left->next;
}
else{
curr->next = right;
right = right->next;
}
curr = curr->next;
}
curr->next = left?left:right;
return new_head->next;
}
};
剑指 Offer 51. 数组中的逆序对
经典的Merge Sort应用,合并两个排序数组时,可以顺便统计逆序对
特别解释一下程序码中更新res的mid-i+1
在tmp[i]>tmp[j]情况下,保证tmp[i]~tmp[mid]都比tmp[j]大,而这些都会形成逆序对,所以逆序对增加mid-i+1!!
有这个理解下,这题只是要实现一下Merge Sort而已
class Solution {
int res = 0;
public:
int reversePairs(vector<int>& nums) {
/*
思路:
merge sort合并两个有数组时计算有多少逆序对
*/
int n = nums.size();
vector<int> tmp(n);
merge_sort(0, n-1, nums, tmp);
return res;
}
void merge_sort(int l, int r,vector<int>& nums, vector<int>& tmp){
if(l>=r){
return;
}
int mid = (l+r)/2; //mid是左数组的尾
merge_sort(l, mid, nums, tmp);
merge_sort(mid+1, r, nums, tmp);
//利用tmp保存两有序数组, tmp[l]~tmp[mid]是左数组, tmp[mid+1]~tmp[r]是右数组
for(int k = l; k<=r; ++k){
tmp[k] = nums[k];
}
int i = l, j = mid+1;
for(int k = l; k<=r; ++k){
if(i>mid){
nums[k] = tmp[j++];
}
else if(j>r){
nums[k] = tmp[i++];
}
else if(tmp[i]<=tmp[j]){
nums[k] = tmp[i++];
}
else{ //tmp[j]<tmp[i] 出现逆序对
nums[k] = tmp[j++];
res+=mid-i+1;
}
}
}
};
Merge Sort的分治思路很容易在题目出现,刷过几题之後出现类似的题目会好思考一点(?
<<: Ruby on Rails Find Find_by Where 差别
Q1. XSS Lab(2)-6 题目:https://alf.nu/alert1 Quine 题目...
继第22篇已经可以绑定fragment跟viewpager那我们就在fragment中加入一些东西吧...
提到健康监控系统,就不可不提鼎鼎大名的《PSYCHO-PASS心灵判官》中的希必拉系统Sibyl S...
云端托管服务 云端托管服务其实相当於使用硬体供应商准备的 Server 来运行我们准备的服务,他们可...
美国国防部在 2020 年1月底公布新规范 「网路安全成熟度模型认证Cybersecurity Ma...