Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
3 4 6
The flattened tree should look like:
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.
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))$.
You may assume nums1 and nums2 cannot be both empty.
cut A and B into two parts:
|A, A, …, A[i-1]||A[i], A[i+1], …, A[m-1]|
|B, B, …, B[j-1]||B[j], B[j+1], …, B[n-1]|
there is two conditions we should make sure:
len(left_part) == len(right_part)
max(left_part) <= min(right_part)
so, for the aboving condition, the equivalent should be：
the condition means 。
then the median of two arrays is:
median = (max(left_part) + min(right_part)) / 2 // when m + n is even
the mission can be solved by the following steps:
- find min(len(array1), len(array2)) and set it to m
- searching i in [0, m] to find the ‘i’ that:
B[j - 1] <= A[i]and
A[i -1] <= B[j]where
j = (m + n + 1)/2 - i
if the time complexity is $ O(log (min(m+n)))$,we should use binary search to find the ‘i’
<1> Set imin = 0, imax = m, then start searching in [imin, imax]
when it comes to eadge values i=0,i=m,j=0,j=n, where** A[i-1],B[j-1],A[i],B[j]** may not exist.