剑指 Offer II 075. 数组相对排序（sort）

  • 对于cmp函数来说，返回true就代表前面应该放在前面，flase则相反。

    1. class Solution {
    2. public:
    3.   vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2){
    4.       unordered_map<int, int> hashset;
    5.       for(int i = 0; i < arr2.size(); i++) {
    6.           hashset[arr2[i]] = i;
    7.       }
    8.       sort(arr1.begin(), arr1.end(), [&](int a, int b){
    9.           if(hashset.count(a)&&hashset.count(b)) {
    10.               return hashset[a] < hashset[b];
    11.           } else if(!hashset.count(a)&&!hashset.count(b)){
    12.               return a < b;
    13.           } else {
    14.               if(hashset.count(a)) {//注意这里的特殊写法
    15.                   return true;
    16.               } else {
    17.                   return false;
    18.               }
    19.           }
    20.       });
    21.       return arr1;
    22.   } 
    23. };

    剑指 Offer II 074. 合并区间（需要看）

    要把很多情况都分清楚
    这里以第一个区间作为排序标准比较好。更加方便比较

    1. class Solution {
    2. public:
    3.   vector<vector<int>> merge(vector<vector<int>>& intervals) {
    4.       sort(intervals.begin(), intervals.end());
    5.       vector<vector<int>> ret;
    6.       vector<int> ser = intervals[0];
    7.       for(int i = 1; i < intervals.size() ; i++) {
    8.           if(ser[1] < intervals[i][0]) {
    9.              ret.push_back(ser);
    10.              ser.clear();
    11.           } else {
    12.               if(ser[1] <= intervals[i][1]) {
    13.                   ser[1] = intervals[i][1];
    14.               }
    15.           }
    16.           if(ser.size() == 0) {
    17.               ser = intervals[i];
    18.           }
    19.       }
    20.       if(ser.size()) {
    21.           ret.push_back(ser);
    22.       }
    23.       return ret;
    24.   }
    25. };

    剑指 Offer II 077. 链表排序（求中点+归并排序）

    1. class Solution {
    2. public:
    3.   ListNode* sortList(ListNode* head) {
    4.       if(!head||!head->next) return head;
    5.       ListNode* mid = getmid(head);
    6.       ListNode* node = mid->next;
    7.       mid->next = nullptr;
    8.       ListNode* node1 = sortList(head),* node2 = sortList(node);
    9.       ListNode* dummy = new ListNode(0);
    10.       ListNode* ret = dummy;
    11.       while(node1&&node2) {
    12.           if(node1->val < node2->val) {
    13.               ret ->next =  node1;
    14.               node1 = node1->next;
    15.           } else {
    16.               ret ->next =  node2;
    17.               node2 = node2->next;
    18.           }
    19.           ret = ret->next;
    20.       }
    21.       //尾巴接上去
    22.       if(!node1) {
    23.           ret->next = node2;
    24.       } else {
    25.           ret->next = node1;
    26.       }
    27.       return dummy->next;
    28.   }
    29.   ListNode* getmid(ListNode* head) {//根据快慢指针获取中点
    30.       ListNode* fast = head, *slow = head;
    31.       while(fast->next&&fast->next->next) {
    32.           slow = slow->next;
    33.           fast = fast->next->next;
    34.       }
    35.       return slow;
    36.   }
    37. };

    剑指 Offer II 078. 合并排序链表（有意义）

    归并排序

    和上题目的写法类似，但是复杂度过高

    1. class Solution {
    2. public:
    3.   ListNode* mergeKLists(vector<ListNode*>& lists) {
    4.       ListNode* dummy = new ListNode(0);
    5.       ListNode* ret = dummy, *node;
    6.       while((node = getnode(lists))) {
    7.           ret->next = node;
    8.           ret = ret->next;
    9.       }
    10.       return dummy->next;
    11.   }
    12.   ListNode* getnode(vector<ListNode*>& lists) {
    13.       ListNode* node = nullptr;
    14.       int idx = 0;
    15.       for(int i = 0; i < lists.size(); i++) {
    16.           if(!lists[i]) continue;
    17.           if(!node) {
    18.               node = lists[i];
    19.               idx = i;
    20.           } else {
    21.               if(node->val > lists[i]->val) {
    22.                   node = lists[i];
    23.                   idx = i;
    24.               }
    25.           }
    26.       }
    27.       if(node) {
    28.           lists[idx] = lists[idx]->next;
    29.       }
    30.       return node;
    31.   }
    32. };

    堆排序

  • 千万注意priority_queue的cmp逻辑是反着来的，node1->val < node2->val是大顶堆，node1->val > node2->val 才是小顶堆。

  • 默认为大顶堆
    1. class Solution {
    2. public:
    3.   struct cmp {
    4.       bool operator()(ListNode* node1, ListNode* node2) {//仿函数写cmp
    5.           return node1->val > node2->val;//这里是小顶堆，因为优先队列就是这样设计的，和正常逻辑相反
    6.       }
    7.   };
    8.   ListNode* mergeKLists(vector<ListNode*>& lists) {
    9.       priority_queue<ListNode*, vector<ListNode*>, cmp> q;
    10.       for(auto list : lists) {
    11.           if(!list) continue;
    12.           q.push(list);
    13.       }
    14.       ListNode *dummy = new ListNode(0);
    15.       ListNode *ret = dummy;
    16.       while(!q.empty()) {
    17.           ListNode* node = q.top();
    18.           q.pop();
    19.           if(node->next) q.push(node->next);
    20.           ret->next = node;
    21.           ret = ret->next;
    22.       }
    23.       return dummy->next;
    24.   }
    25. };