Divide and conquer

Posted on Edited on In ,

Overview

  1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
  2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
  3. Combine the solutions to the subproblems into the solution for the original problem.

Samples and exercise

Decrease the time from $O(n)$ to $O(log(n))$

No.4 Median of Two Sorted Arrays
This exercise need we use binary search to find the proper value.

Majority elements

If an element is the majority element(appears more than n/2 times), it should be the majority element in the left half sequence or in the right sequence, otherwise it cannot be the majority element.

Quick sort

Binary sort.

Merge sort

Merge two in-order sequence to a whole sequence. The best time is $O(nlog(n))$

No.23 Merge k Sorted Lists

Number of inverse pairs

Reference

[1] https://blog.csdn.net/xlinsist/article/details/79198842
[2] https://blog.csdn.net/qq_29793171/article/details/80057088