Leetcode 4: Median of two sorted array - a warmup practice

May 15, 2015

Review the leetcode 4: Median of two sorted array, warm up the algorithm.

Here is the last practice:

https://github.com/jianminchen/Leetcode_C-/blob/master/4MedianOfTwoSortedArrays.cs

Step 1: 
Read the last practice 10 - 20 minutes on May 15, 2016
-- write down the ideas: 
1. Brute force solution: O(nlogn)
2. Linear solution: O(n) 

3. Transform to the kth element problem first, and then: 
Try to get rid of k/2 elements once, so the algorithm will go to logk, k = (m+n)/2 

Some analysis and reasoning: 
Assuming that A and B both arrays are with length > k/2, and then, compare A[k/2-1] and B[k/2-1]. 

Read the blog again:
http://blog.csdn.net/yutianzuijin/article/details/11499917

http://blog.csdn.net/zxzxy1988/article/details/8587244

Step 2: 
Spend 30 minutes to read and then write some code. 

Related to Leetcode 215: Find kth largest element in the array. 


Question and Answer:

1. Write down what you learn through this practice.
Answer: The algorithm is very well defined, is a special case of find kth element in two sorted arrays.

2. Algorithms learning and important thing to learn:

Answer:
1. Always know how to solve the problem using naive solution, brute force one first.

O(nlogn) -> O(n) -> O(log(m+n)/2)

2. And then, discuss the improvement.