06.Sort.md

Sort an array

• 0912.Sort an Array （M）
  Solution: bubble sort, quick sort，merge sort.
• 0148.Sort_List (!!M)
  Solution: merge sort算法, 不能用quick sort，因为quick sort交换在list中很麻烦, 注意找中点的时候，slow, fast = head, head.next。如果写成slow, fast = head, head会陷入死循环.
• 0179. Largest_Number.py (!!M)
  Solution: remember compare 的写法
• 0969.Pancake_Sorting.py （M Pramp）
  Solution: for i in range(lens-1, -1, -1 ): Find maxIndex -> flip max to top -> flip max to bottom of the whole arr -> repeat.
• 0280.Wiggle_Sort.py （M Pramp）
  O(N): 从左到右扫一遍，不满足条件的交换就好了。定义一个变量prevShouldLessThanCurr, in the for loop, prevShouldLessThanCurr = not prevShouldLessThanCurr every step, and based on prevShouldLessThanCurr is true or not, we swap nums[i-1] with nums[i] or not.
• 0324.Wiggle_Sort_II.py （M）
  这题比Wiggle Sort I难在相邻的数不能相等，所以相邻交换法行不通， 我们可以sort the nums, then 把有序数组从中间分成两部分，然后从前半段的末尾取一个，在从后半的末尾取一个，这样保证了第一个数小于第二个数，然后从前半段取倒数第二个，从后半段取倒数第二个，这保证了第二个数大于第三个数，且第三个数小于第四个数，以此类推。O(nlogn), O(n). Follow up:https://leetcode.com/problems/wiggle-sort-ii/discuss/77677/O(n)%2BO(1)-after-median-Virtual-Indexing
• Sort_a_nearly_sorted_or_K_sorted_array.py （M）
  题目要求sort一个长程无序短(k)程有序的数组，solution: 用一个大小为k的heapq存储k个元素，然后i从k开始遍历nums, 遍历的过程中每次都更新nums的最左边: nums[target_idx] = heappop(hq)，同时更新hq: heappush(hq, nums[i]), 这么做成立的原因是i是从k开始遍历的，所以nums[i]一定是大于nums[0]的，而nums[0]>=heappop(hq), 所以nums[i]及其后面的数一定是大于heappop(hq)的，所以可以放心地把heappop(hq)放到target_idx的位置。时间复杂度是O(nlogk). 当k=1: O(0), 当k=n: O(nlogn), 当k=n时就degrade成了heap sort了
• 0451.Sort_Characters_By_Frequency.py （M）
  Solution: buckets sort.
• 0143.Reorder_List （M）
  Solution: step 1: cut the list into two halves; step 2: reverse the 2nd half; step 3: connect the 1st and 2nd half
• 0061.Rotate_List.py （M）
  Solution:先求出长度，在根据lens - k % lens得到第几个元素是新的head
• 0561.Array_Partition_I.py （E）
  

Quick sort

• 0031.Partition_Array.py （E）
  用quick select的模板，partition这个函数的作用是O(N)找到某个数k在一个无序数组中所在的位置，并按照这个数k将该数组分为左右两部分。
• 0905.Sort_Array_By_Parity.py （E）
  solution 1: 同向双指针； solution 2: 反向双指针 - partition 好像两种方法都不能maintain the original order of numbers. 貌似同向双指针可以maintain the original order of numbers.
• 0075.Sort_Colors.py （!!M）
  solution 1: 同向双指针: step 1: move all 0s to the left; step 2: move all 1s to the left of the rest of the arr; 优点：very easy to implement, don't need to memorize anything. Solution 2: 经典的荷兰三色旗问题采用 Dijkstra's 3-way partitioning: while i <= gt: a[i] < pivot: exchange a[i] and a[lt] and i++, lt++; a[i] > pivot: exchange a[i] and a[gt] and gt--; a[i] = pivot: i++; QuickSort with 3-way partitioning is very fast because it is entropy optimal
• 0144.Interleaving_Positive_and_Negative_Numbers.py （Lintcode）
  STEP 1: 反向双指针（或同向双指针）对[-1,-2,4,,5,-3,6]进行partition，负数在左边，正数在右边[-1, -2, -3, 4, 5, 6]; STEP 2: 再正负正负安插.
• 0215.Kth_Largest_Element_in_an_Array.py （!!M）
  solution 1: heapq, time: O(N+KlogK), N 来自于for循环，logK来自于heap的长度是K，heap 的push 和pop都是logK; heapq适合做第K大，第K小，前K大，前K小问题; solution 2: quick select: O(N) - O(N^2). solution 3: bucket sort O(N). use frequency as idx to store number.
• 0453.Minimum_Moves_to_Equal_Array_Elements.py （!!M）
  给 n-1 个数字加1，效果等同于给那个未被选中的数字减1， 比如数组 [1，2，3]，给除去最大值的其他数字加1，变为 [2，3，3]，等价于最大的数减一变为 [1，2，2]， 那么问题也可能转化为，将所有数字都减小到最小值.
• 0462.Minimum_Moves_to_Equal_Array_Elements_II.py （!!M）
  solution 1: find median by sorting; solution 2: find meddian by quick select(kth largest element) - O(N)

merge sort

• Algorithm: devide and conquer

• 0088.Merge Sorted Array (M)
  Solution: 将小数组归并到大数组里，从后往前merge
• 0023.Merge_k_Sorted_Lists.py (M)
  正解 Solution 1: divide and conquer. solution 2: maintain一个heapq，初始化将每个list的head放入，然后每次pop出一个最小的，再把最小的那个的.next push进heapq, O(NlogK); we need to override ListNode compare function __ lt __ to make customized compare happens: compare ListNode.
• 0148.Sort_List.py (M)
  Solution1: divide and conquer.先找到中点 slow = head, fast = head.next rightHead = slow.next

Bucket Sort - use freq/dist/num as idx

• 0451.Sort_Characters_By_Frequency.py (!!M)
  solution 1: use hash map, and then convert to list, then sort, then conver to string - O(nlogn). solution 2: bucket sort: putting our chars in buckets/indexes based on their frequency - O(N).
• 0215.Kth_Largest_Element_in_an_Array.py （!!M）
  solution 1: heapq, time: O(N+KlogK), N 来自于for循环，logK来自于heap的长度是K，heap 的push 和pop都是logK; heapq适合做第K大，第K小，前K大，前K小问题; solution 2: quick select: O(N) - O(N^2). solution 3: bucket sort O(N). use frequency as idx to store number.
• 0347.Top_K_Frequent_Elements.py （!!M）
  需要一个freqDict来记录每个数出现的freq， heapq, heapq中放入的是(freq, key)对; 按照freq来做heapq，这样就保证了可以筛选出most freqent k item; solution 2: quick select should implement; solution 3: bucket sort O(N) faster then solution 2, cuz solution 2 is O(N^2) in worst case. use the freq as index for the bucket.
• Pramp__121820__Word-Count-Engine.py （M）
  use freq as idx to do bucket sort.
• 0791.Custom_Sort_String.py （!!M）
  Bucket sort. use a bucket with bucket size n+1, store all the ch in t that also appear in s to the corresponding bucket_id, and those didn't appear in s to the last bucket_id. O(M+N)
• 0217.Contains_Duplicate.py （E）
  hash set to store the seen number, if seen again, return True. Warm up for 219
• 0219.Contains_Duplicate_II.py（E）
  solution 1: dictionary to store the (num, pos) pairs. O(N), O(M), where N is the number of num in nums, M is the number of distinct num in nums; solution 2: sliding window: use a numSet to fix the sliding window to be k. O(N), O(k), where k is the size of the window. Warm up for 220
• 1057.Campus_Bikes.py（!!!M）
  brutal force solution O(MNlog(MN)): find the distance of all combinations, and sort them. . bucket sort solution O(MN): find the distance of all combinations, and put them into bucket based on their distance. In this way, the distances are represented by idx, which were sort by nature.

Cyclic Sort 把数当坐标用

• 0448.Find_All_Numbers_Disappeared_in_an_Array.py（E）
  难就难在题目要求O(1) space. 做法是把数组里的数当坐标用，We use the sign of the index as the indicator. If one number never occur, we know the number corresponding to the idx will never be negative. eg: [4,3,1,3] -- > [-4,3,-1,-3], 2 is missing, so num[2-1] will never be changed to be negative. 1st pass: change numbers to be negative [4,3,1,3] --> [-4,3,-1,-3]. 2nd pass: find those numbers that has not been changed negative, there is not num corrsponding to their idx.
• 0442.Find_All_Duplicates_in_an_Array.py（M）
  Solution 1: counter Solution 2: hashset Solition 3: use arr index to present the element
• 0287.Find_the_Duplicate_Number.py（M）
  通过位置i指向nums[i]的边建立一个图，因为有数字出现多次，那么这个图一定存在环，而且环的入口处就是重复的数，通过快慢指针的方法来找环的入口
• 0268.Missing_Number.py（M）
  solution 1: 448类似的做法，我们通过nums[i] += 1来change all 0s to be positive number. solution 2: bit manipulation 所有的idx and num都异或起来. solution 3: 题目确定只有一个missing number. add every num together and compare with n(n+1)/2. O(1). Follow up: what is there are 2 missing numbers? How can we solve within O(1). we can calculate the sum of the 2 missing numbers using solutino 3, and also prodct of the 2 missing number, then 用求根公式求出来就可以了

Sorted Array

• 1051.Height_Checker.py（E）
  just check 谁不在他该有的位置
• 0561.Array_Partition_I.py（E）
  sort the arr first, then the maximum sum of pairs is the sum of every other num.
• 0004.Median_of_Two_Sorted_Arrays.py （!!H）
  midIdx1, midIdx2 = len(nums1)//2, len(nums2)//2; midVal1, midVal2 = nums1[midIdx1], nums2[midIdx2]; when k is relatively large, then we can safely drop the first half that are surely smaller than the kth, the question is where is the first half that are surely smaller than the kth? by comparing midVal1 and midVal2, we can find it out, if midVal1 < midVal2, then all the vals in nums1[:midIdx1] are less than midVal2, also all of those vals are less than kth, we can safely drop all those vals
• 0455.Assign_Cookies.py（E）
  greedily 尽量用最少的糖果去优先满足孩子孩子，所以需要先排序
• 0406.Queue_Reconstruction_by_Height.py（!!M）
  Greedy: Since short people will not disturb/affect the relative order of taller people so we can start from tallest guy(s). Then for each person [i,j], we insert it into res based on j.
• 1029.Two_City_Scheduling.py（M）
  像这种interval的题一般都需要先排个序，排序标准很重要，排序标准：去city A比去city B多用多少钱，这样一来去排在前面的就是去city A能省下最多钱的人，让前N个人都去A就能省下最多的钱