hoho的日子

Algorithm Time Complexity Space Complexity Best Average Worst Worst Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n)) Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n) class Solution(object):     def sortIntegers1(self, A):         # merge sort         # https://www.geeksforgeeks.org/merge-sort/         def merge(left, right):             llen, rlen = len(left), len(right)             l, r = 0, 0             result = []             while l < llen and r < rlen:                 if left[l] <= right[r]:                     result.append(left[l])   ...

In Leetcode Binary Search problems, it provide better search O(log n) instead of O(n) regular search. [ basically, steps are ] 1. determine low and high starting value 2. set mid equal (low + high) / 2 2. give a while loop when low < high 3. return target value if found else increase low or reduce high's value base on mid [ why those steps ] first, it's important to know the range we are going to search. then we can choose the middle element compare list[mid] with target and then adjust low or high. Said you want to find 83 in a list from [1,2,...,100], you only need log2 100 ~= 6.6 times search which much better than 100 times, right? [ 153. Find Minimum in Rotated Sorted Array ] Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ). Find the minimum element. You may assume no duplicate exists in the array. 1.low = 0 , high = length of list - 1...