努橙刷题编: [笔记整理] 九章算法第二章 Binary Search & Sorted Array Part2
1. Search for a Range <=> How many times did a number appear? range[x1, x2] => x2-x1+1
* The insertion position may not be in current array
* Find the insertion position, 3 positions to check: x<start, start<x<end, x>end
* No duplicate
* 2 possible position for mid: [mid] >= [0], [mid] < [0]
* 4 possible position for target: [0]<T<[mid], [0]<[mid]<T, T<[mid]<[0], [mid]<T<[0]
* Duplicate
* Worst case for binary search - O(n) e.g. If in every iteration, [mid]==[0]/[mid]==[length-1] =>O(n)
* Any element in row1 < Any element in row 2
* Use binary search for 2 times, 1st time find the row of target, 2nd time find the column of target
[1 0 2 4]
[1 2 6 9]
[3 5 7 10]
[7 8 9 11]
* Quadrate search O(n)
* Search from left bottom to right top, exclude 1 row/column each iteration, O(m + n)
* peak <=> A[p] > A[p - 1] && A[p] >A[p + 1]
9. Remove Duplicate from Sorted Array
10. Remove Duplicate from Sorted Array II
11. Merge Sorted Array
* Merge + Find O(m + n)
* Find kth largest O(logn)
when (m+n) is odd=>k=(m+n)/2+1
when (m+n) is even=>k1=(m+n)/2, k2=(m+n)/2+1
* How to find kth largest?
Throw away each k/2 elements in each iteration
* Sort, O(1) space O(nlogn) time
* 3 times reverse, O(1) space O(n) time
* abcdefg, offset=3 => efgabcd
* reverse each word, then reverse the entire string
Read full article from 努橙刷题编: [笔记整理] 九章算法第二章 Binary Search & Sorted Array Part2
No comments:
Post a Comment