365天挑战LeetCode1000题——Day 111 归并排序 II

148. 排序链表

代码实现

/*** 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 {
private:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* pl1 = l1, *pl2 = l2;ListNode* ans = new ListNode();ListNode* curNode = ans;while (pl1 && pl2) {ListNode* tmp;if (pl1->val <= pl2->val) {tmp = new ListNode(pl1->val);pl1 = pl1->next;}else {tmp = new ListNode(pl2->val);pl2 = pl2->next;}curNode->next = tmp;curNode = tmp;}if (pl1) {curNode->next = pl1;}else {curNode->next = pl2;}return ans->next;}
public:ListNode* sortList(ListNode* head) {if (!head) return head;ListNode* dummyHead = new ListNode(-1, head);int length = 0;ListNode* cur = head;while (cur) {length++;cur = cur->next;}for (int curLength = 1; curLength < length; curLength *= 2) {ListNode* curr = dummyHead;ListNode* prev = dummyHead;while (curr) {ListNode* head1 = curr->next;for (int i = 0; i < curLength && curr; i++) {curr = curr->next;}if (!curr || !curr->next) break;ListNode* head2 = curr->next;curr->next = nullptr;curr = new ListNode(-1, head2);for (int i = 0; i < curLength && curr; i++) {curr = curr->next;}if (!curr || !curr->next) {prev->next = mergeTwoLists(head1, head2);break;}else {ListNode* tmp = curr->next;curr->next = nullptr;prev->next = mergeTwoLists(head1, head2);while (prev->next) prev = prev->next;prev->next = tmp;curr = prev;}}}return dummyHead->next;}
};

315. 计算右侧小于当前元素的个数

代码实现

class Solution {
private:vector<int> ans;void mergeSort(vector<pair<int, int>>& tokens, vector<pair<int, int>>& tmp,int l, int r) {// cout << l << " " << r << endl;if (l == r) return;int m = (l + r) >> 1;mergeSort(tokens, tmp, l, m);mergeSort(tokens, tmp, m + 1, r);int i = l, j = m + 1, pos = l;while (i <= m && j <= r) {if (tokens[i].first <= tokens[j].first) {tmp[pos++] = tokens[i];ans[tokens[i].second] += j - m - 1;i++;}else {tmp[pos++] = tokens[j];j++;}}while (i <= m) {tmp[pos++] = tokens[i];ans[tokens[i].second] += j - m - 1;i++;}// cout << "w" << endl;while (j <= r) {tmp[pos++] = tokens[j];j++;}copy(tmp.begin() + l, tmp.begin() + r + 1, tokens.begin() + l);}
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();vector<pair<int, int>> tokens;for (int i = 0; i < n; i++) {tokens.push_back({nums[i], i});}vector<pair<int, int>> tmp(n);ans = vector<int>(n);mergeSort(tokens, tmp, 0, n - 1);return ans;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！