{"id":871,"date":"2020-03-29T12:02:57","date_gmt":"2020-03-29T19:02:57","guid":{"rendered":"http:\/\/209.126.2.187\/?p=871"},"modified":"2020-03-29T12:03:27","modified_gmt":"2020-03-29T19:03:27","slug":"merge-sort","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/03\/29\/merge-sort\/","title":{"rendered":"Merge Sort"},"content":{"rendered":"\n

Summary<\/h2>\n\n\n\n

In this post, I will introduce some problems using the merge sort technique. <\/p>\n\n\n\n

These problems often ask, for an element at index \"i\", how many \"j\" are there which satisfies a formula. <\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t\n\t\n\t\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
LC 1395 <\/a><\/td>Enumerate the middle element + Count #elements larger or smaller
\n<\/td>		6 points<\/td>\n<\/tr>\n
LC 327 <\/a><\/td>Prefix sum + Keep diff in range<\/td>6-7 points<\/td>\n<\/tr>\n
LC 493 <\/a><\/td>Count #elements larger or smaller<\/td>6 points<\/td>\n<\/tr>\n
LC 315 <\/a><\/td>Count #elements larger or smaller<\/td>6 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

The Master Theorem<\/h4>\n\n\n\n

<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[T(n) = a\times(T(\frac{n}{b})) + f(n)\]\"<\/p><\/p>\n\n\n\n

If \"f(n)\" is of complexity \"O(n^{log_b^a})\", then \"T(n)\" is of complexity \"O(n^{log_b^a}\times logn)\"<\/p>\n\n\n\n

So in these problems, a key point is to keep the merge part of complexity \"O(n)\" by leveraging the sorted property. <\/p>\n\n\n\n

Keep Difference in Range<\/h4>\n\n\n\n

I want to talk about the merge part of LC 327<\/a> in this section. Given two sorted array \"nums[left:mid]\" and \"nums[mid+1:right]\", the problem is to count how many \"\{i,\ j\}\" are there, such that<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[lower <= nums[j] - nums[i] <= upper, i \in [left:mid]\ and\ j \in [mid+1:right]\]\"<\/p><\/p>\n\n\n\n

Usually, we will enumerate the left part (or the right part) by \"i\". We use two cursors \"start\" and \"end\" to store the boundary in the right part to satisfy the above formula.<\/p>\n\n\n\n

int mid = left + (right - left) \/ 2;\nint result = merge_sort(left, mid, nums) + merge_sort(mid + 1, right, nums);\nint start = mid + 1, end = mid + 1;\nfor (int i = left; i < mid + 1; ++i) {\n    while (start < right + 1 && (long)nums[start] - nums[i] < lower) {\n        start++;\n    }\n    while (end < right + 1 && (long)nums[end] - nums[i] <= upper) {\n        end++;\n    }\n    result += (end - start);\n}\ninplace_merge(nums.begin() + left, nums.begin() + mid + 1, nums.begin() + right + 1);\nreturn result;<\/code><\/pre>\n\n\n\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Summary In this post, I will introduce some problems using the merge sort technique. These problems often ask, for an element at index , how many are there which satisfies a formula. OJ Details The Master Theorem     If is of complexity , then is of complexity So in these problems, a key point…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56],"tags":[],"class_list":["post-871","post","type-post","status-publish","format-standard","hentry","category-sort"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/871","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=871"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/871\/revisions"}],"predecessor-version":[{"id":885,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/871\/revisions\/885"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=871"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=871"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=871"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}