LeetCode brush notes sorting algorithm merge sorting

Introduction to merge sort

Algorithm idea:

The core idea of merge sort is to use divide and conquer strategy to classify the sort task of the whole array into two sub problems, the first half sort and the second half sort, and then integrate the two ordered parts to complete the overall sort. That is, the array is divided into several subsequences until a single element forms a sequence, and then the sequences obtained in each stage are combined to obtain the final complete sorting sequence.

Merging and sorting tasks can be completed as follows:

1. Sort the first half
2. Sort the last half
3. Merge the two halves into a new ordered array, then copy back to the original array, and sort it.

Execution example:

Input: [29,10,14,37,14,25,10]

Algorithm implementation:

// Merge the local a[s,m] and a[m+1,e] of array a into tmp, ensure the order of tmp, and then copy back to a[s,m]
void merge(vector<int>& arr, int start, int mid, int end, vector<int> tmp){
    int pTmp = 0;
    int pLeft = start; int pRight = mid+1;
    while(pLeft<=mid&&pRight<=end){
        if(arr[pLeft] < arr[pRight]){
            tmp[pTmp++] = arr[pLeft++];
        }else{
            tmp[pTmp++] = arr[pRight++];
        }
    }
    while(pLeft<=mid){
        tmp[pTmp++] = arr[pLeft++];
    }
    while (pRight<=end)
    {
        tmp[pTmp++] = arr[pRight++];
    }
    for(int i=0;i<pTmp;i++){
        arr[start+i] = tmp[i];
    }
}

// Merge sort recursive calls, first in the first half, in the second half, and finally merge the results of the two parts
void mergeSort(vector<int>& arr, int start, int end, vector<int> tmp){
    if(start < end){
        int mid = start + (end-start)/2;
        mergeSort(arr,start,mid,tmp);
        mergeSort(arr,mid+1,end,tmp);
        merge(arr,start,mid,end,tmp);
    }
}

493 flip pair

Given an array num, if I < J and num [i] > 2 * num [J], call (i,j) a flipped pair and return the number of flipped pairs in the given array.

Input an array and output an integer to represent the number of flipped pairs in the array

Input: [2,4,3,5,1]
Output: 3
Explanation: (4,1), (3,1), (5,1) three flip number pairs

Resolution:

The essence of this problem is to find the number in reverse order in the array, but there is a new definition of the number in reverse order in this problem.

Based on the merge sorting algorithm, we adopt the divide and conquer strategy: divide the arrangement into two parts, first find the flip pair of the left half, and then find the flip pair of the right half; Finally, the time complexity O(nlogn) of the flip pair between the two parts is calculated.

The left and right sides are arranged in order. For example, they are sorted from large to small. You only need to scan the left and right sides from beginning to end to find the flip logarithm composed of one number on each side.

An easy to understand implementation method is given below. A small modification is made on the basis of merging and sorting code, that is, when the element on the left is larger than that on the right, start looking for flip pairs. However, the maximum data size of this problem can reach 50000. If this simple loop traversal is used, it will lead to timeout.

class Solution {
public:
    void mergeAndCount(vector<int>& nums, int start, int mid, int end, vector<int> tmp, int& count){
        if(start>end) return;
        int pTmp = 0;
        int pLeft = start, pRight = mid+1;
        while(pLeft<=mid && pRight<=end){
            if(nums[pLeft] < nums[pRight]){
                tmp[pTmp++] = nums[pLeft++];
            }else{
                // This loop traversal method will cause a timeout
                for(int i=pLeft;i<=mid;++i){
                    if(nums[i] > (long long)2*nums[pRight]){
                        ++count;
                    }
                }
                tmp[pTmp++] = nums[pRight++];
            }
        }
        while(pLeft<=mid){
            tmp[pTmp++] = nums[pLeft++];
        }
        while(pRight<=end){
            tmp[pTmp++] = nums[pRight++];
        }
        for(int i=0;i<pTmp;++i){
            nums[start+i] = tmp[i];
        }
    }

    void mergeSort(vector<int>& nums, int start, int end, vector<int> tmp, int& count){
        if(start<end){
            int mid = start + (end-start)/2;
            mergeSort(nums,start,mid,tmp,count);
            mergeSort(nums,mid+1,end,tmp,count);
            mergeAndCount(nums,start,mid,end,tmp,count);
        }
    }

    int reversePairs(vector<int>& nums) {
        int ans = 0;
        vector<int> tmp(nums.size());
        mergeSort(nums,0,nums.size()-1,tmp,ans);
        return ans;
    }
};

In order to reduce the time complexity, we adopt the following strategy: if the left half A1 and the right half A2 are ordered, we can solve this problem in linear time. Of course, it can also be solved by binary search, but the time complexity is linear logarithm.

Initialize two pointers i and j pointing to the headers of A1 and A2 respectively
If A1[i] > 2 * A2 [j], then A1[i] and all subsequent elements meet the requirements. Update the answer and move back j; otherwise, move back I
Finally, merge A1 and A2 to solve the following larger sub problems, and return the previous results

class Solution {
public:
    int find_reversed_pairs(vector<int>& nums, int start, int end){
        int res = 0,mid = start + (end-start)/2;
        int i = start,j = mid+1;
        for(;i <= mid;i++){
            while(j <= end && (long)nums[i] > 2*(long)nums[j]) {
                res += mid - i + 1;
                j++;
            }
        }
        return res;
    }
    
    int merge_sort(vector<int>& nums, int start, int end, vector<int> tmp){
        if(start >= end) return 0;
        int mid = start + (end-start) / 2;
        
        int res = merge_sort(nums,tmp,start,mid) + 
                  merge_sort(nums,tmp,mid+1,end) + 
                  find_reversed_pairs(nums,start,end);
        
        int i = start,j = mid+1,ind = start;
        
        while(i <= mid && j <= end){
            if(nums[i] <= nums[j]) tmp[ind++] = nums[i++];
            else tmp[ind++] = nums[j++];
        }
        while(i <= mid) tmp[ind++] = nums[i++];
        while(j <= end) tmp[ind++] = nums[j++];
        
        for(int ind = start;ind <= end;ind++) nums[ind] = tmp[ind];
    
        return res;
    }
    
    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int>& tmp(nums.size());
        return merge_sort(nums,0,nums.size()-1,tmp);
    }
};

148 sorting linked list

Given the head node of the linked list, please arrange it in ascending order and return the sorted linked list. It is required to be completed within the time complexity of O(nlogn).

Input a linked list and output a linked list arranged in ascending order.

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Resolution:

You can try before you finish the problem 21 merge two ordered linked lists,23 merge K ascending linked lists Two questions may help you solve this problem.

We can use the idea of merging and sorting to complete this problem. Using divide and conquer strategy, the linked list is divided into two parts, and then sorted in each part. Therefore, we need to complete the following two tasks:

Find the midpoint of the linked list and divide the linked list
Sort the local linked list and merge the results

The first task can be completed by using the fast and slow pointer. The fast pointer takes two steps at a time and the slow pointer takes one step at a time. In this way, when the fast pointer reaches the end of the linked list, the slow pointer just points to the midpoint of the linked list. Then, we recursively use the appeal method to divide the linked list into smaller subproblems until it can no longer be divided. Here we need to pay attention to a common mistake: when looking for the midpoint, we can't directly judge whether the fast pointer reaches the end point with nullptr, but compare it with the tail node at the end of the list.

The second task is to merge the linked list in ascending order: after the segmentation is completed, iteratively merge the two parts of the linked list, merge the linked list in ascending order, and finally form a complete ascending linked list.

class Solution {
public:
	// Merge two linked lists
    ListNode* merge(ListNode *l1, ListNode *l2){
        if(!l1 || !l2) return l1?l1:l2;
        ListNode dummy;
        ListNode *tail = &dummy;
        ListNode *p1 = l1, *p2 = l2;
        while(p1 && p2){
            if(p1->val < p2->val){
                tail->next = p1;
                p1 = p1->next; 
            }else{
                tail->next = p2;
                p2 = p2->next;
            }
            tail = tail->next;
        }
        tail->next = p1?p1:p2;
        tail = nullptr;
        return dummy.next;
    }
	
    // Find the end point of the linked list and recursively divide the linked list
    ListNode* mergeSort(ListNode* head, ListNode* tail){
        if(!head) return nullptr;
        if(head->next == tail){
            head->next = nullptr;
            return head;
        }

        ListNode *slow = head, *fast = head;
        // //Wrong demonstration will lead to cross-border
        // while(fast&&fast->next){
        //     fast = fast->next->next;
        //     slow = slow->next;
        // }
        while(fast != tail){
            slow = slow->next;
            fast = fast->next;
            if(fast != tail){
                fast = fast->next;
            }
        }
        ListNode* mid = slow;
        return merge(mergeSort(head,mid),mergeSort(mid,tail));
    }

    ListNode* sortList(ListNode* head) {
        return mergeSort(head,nullptr);
    }
};