题解

  • 4 Median of Two Sorted Arrays
    • O(log(min(m, n))) time. Determine array B’s index using array A’s index.
  • 33 Search in Rotated Sorted Array
    • No duplicate, four cases: «, <>, ><, and » (not possible).
  • 34 Find First and Last Position of Element in Sorted Array
  • 35 Search Insert Position
  • 50 Pow(x, n)
  • 69 Sqrt(x)
  • 74 Search a 2D Matrix
    • The matrix is a sorted array if rows are concatenated.
  • 81 Search in Rotated Sorted Array II
    • With duplicate, O(n) worst time.
    • Nine cases combined by <, = and >. » is not possible and == is unknown.
  • 153 Find Minimum in Rotated Sorted Array
  • 154 Find Minimum in Rotated Sorted Array II
  • 162 Find Peak Element
    • Peak element is greater than its neighbors. nums[i] != nums[i + 1]. nums[-1] = nums[n] = -inf.
    • Invariant: search interval’s two ends are always lower ones.
  • 222 Count Complete Tree Nodes
    • Binary search on leaf positions according to depth.
  • 240 Search a 2D Matrix II
    • The matrix’s rows and columns are sorted.
    • O(m + n) time, walk from right-up.
    • O(min(m, n)) time divide & conquer.
  • 275 H-Index II
    • Given citations sorted in ascending order, find H-index.
  • 302 Smallest Rectangle Enclosing Black Pixels
    • O(mlog(n)) time by binary search. Project black pixels onto x and y dimensions, and search the bound.
  • 327 Count of Range Sum
    • Given a number array, count different range sums.
    • O(nlog(n)) time by using balanced BST-alike data structure. Trie is also ok.
    • By introducing prefix sums, this is a typical 1D/1D DP problem whose updating process can be optimized by BIT. Need discretization.
  • 410 Split Array Largest Sum
    • Given a number array, split it into m subarrays, find the minimum of the maximum of subarray sum.
    • O(n*sumofarray) time, binary search on answer.
    • O(nmlog(n)) time, 2D/1D DP, updating process optimized with binary search.
  • 436 Find Right Interval
    • Given intervals, for each interval find smallset one who is at the right of it.
    • O(nlog(n)) time, use set’s lower_bound.
  • 540 Single Element in a Sorted Array
    • Given array like 1 1 2 2 3 4 4 5 5, find 3.
    • Binary search on 2*k indices. Find whether nums[i] == nums[i + 1].
  • 658 Find K Closest Elements
    • Binary search for origin and expand.
  • 1011 Capacity To Ship Packages Within D Days
    • Packages are given in a number array.