6. 분치사상

Divide: 문제를 일부 하위 문제로 나누는데 하위 문제의 형식은 원래 문제와 마찬가지로 규모가 더 작다

Conquer: 하위 문제를 차례로 구해냅니다.만약 하위 문제의 규모가 충분하게 작다면, 귀속을 멈추고 해답을 구하세요..

Combine: 하위 문제의 해를 원래 문제의 해로 합친다

두 갈래 나무의 DFS 중 전서, 중서, 후서는 사실상 분치 사상을 이용했다.
148. Sort List
체인 테이블 병합 정렬 사용

class Solution {
public:
    ListNode* sortList(ListNode* head) {
       if (!head || !head->next) return head;
       ListNode preHead = ListNode(INT_MIN);
       preHead.next = head;
       ListNode *preMid = &preHead, *mid = head;
       while (head && head->next) {
           preMid = mid;
           mid = mid -> next;
           head = head -> next -> next;
       }
       
       preMid -> next = NULL;
       return merge(sortList(preHead.next), sortList(mid));
    }
    
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode preHead = ListNode(INT_MIN);
        ListNode *pt = &preHead;
        while (left && right) {
            if (left->val < right->val) {
                pt -> next = left;
                left = left -> next;
            } else {
                pt -> next = right;
                right = right -> next;
            }
            pt = pt->next;
        }
        
        pt->next = left?left:right;
        return preHead.next;
    }
};

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

서열을 찍은 두 개의 수조 중의 k대 원소를 찾아라.이것은 분치사상이 아니라 이분찾기와 같아야 한다. 왜냐하면 모든 자식 문제에는 단지 하나의 자식 문제만 있기 때문이다.
모든 하위 문제의 k개 또는 m+n-k 요소를 제거하는 것을 주의하십시오.두 개의 수조의 두 원소를 비교하면 큰 수조의 큰 부분은 빼고 작은 수조의 작은 부분은 뺀다.

A[0], A[1], ... , A[pa-1], ... A[m-1]
B[0], B[1], ... , B[pb-1], ... B[n-1]

그중 B[pb-1],...B[n-1]의 길이에 A[0],...A[pa-1]의 길이는 k입니다.A[pa-1] > B[pb-1]의 경우 B[pb-1]만 유지됩니다.B[n-1]와 A[0],...A[pa-1] A[pa-1] class Solution { public: // common solutin to get the k-th element in sorted array. k belongs to [1, n] double findMedianSortedArrays(vector& nums1, vector& nums2) { int m = nums1.size(), n = nums2.size(); int len = m + n; if (len & 1) return helper(nums1, nums2, len / 2 + 1); else return (helper(nums1, nums2, len / 2) + helper(nums1, nums2, len / 2 + 1)) / 2; } double helper(vector nums1, vector nums2, int k) { int m = nums1.size(), n = nums2.size(); if (m > n) return helper(nums2, nums1, k); if (m == 0) return nums2[k - 1]; if (k == 1) return min(nums1[0], nums2[0]); int pa = min(k / 2, m), pb = k - pa; if (nums1[pa - 1] < nums2[pb - 1]) { nums1.erase(nums1.begin(), nums1.begin() + pa); nums2.erase(nums2.begin() + pb, nums2.end()); return helper(nums1, nums2, k - pa); } else if (nums2[pb - 1] < nums1[pa - 1]) { nums2.erase(nums2.begin(), nums2.begin() + pb); nums1.erase(nums1.begin() + pa, nums1.end()); return helper(nums1, nums2, k - pb); } else { return nums1[pa - 1]; } } };