Top K


https://mp.weixin.qq.com/s/FFsvWXiaZK96PtUg-mmtEw
面试中,TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,

三、堆
思路:只找到TopK,不排序TopK。

先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素

接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。

时间复杂度:O(n*lg(k))

分治法(Divide&Conquer),把一个大的问题,转化为若干个子问题(Divide),每个子问题“”解决,大的问题便随之解决(Conquer)。这里的关键词是“都”。从伪代码里可以看到,快速排序递归时,先通过partition把数组分隔为两个部分,两个部分“都”要再次递归。

分治法有一个特例,叫减治法

减治法(Reduce&Conquer),把一个大的问题,转化为若干个子问题(Reduce),这些子问题中“”解决一个,大的问题便随之解决(Conquer)。这里的关键词是“只”

二分查找binary_search,BS,是一个典型的运用减治法思想的算法

int BS(int[]arr, int low, inthigh, int target){
         if(low> high) return -1;
         mid= (low+high)/2;
         if(arr[mid]== target) return mid;
         if(arr[mid]> target)
                   return BS(arr, low, mid-1, target);
         else
                   return BS(arr, mid+1, high, target);
}

从伪代码可以看到,二分查找,一个大的问题,可以用一个mid元素,分成左半区,右半区两个子问题。而左右两个子问题,只需要解决其中一个,递归一次,就能够解决二分查找全局的问题。

通过分治法与减治法的描述,可以发现,分治法的复杂度一般来说是大于减治法的
快速排序:O(n*lg(n))
二分查找:O(lg(n))

问题变成了arr[1, n]中找到第k大的数

再回过头来看看第一次partition,划分之后:
i = partition(arr, 1, n);
  • 如果i大于k,则说明arr[i]左边的元素都大于k,于是只递归arr[1, i-1]里第k大的元素即可;
  • 如果i小于k,则说明说明第k大的元素在arr[i]的右边,于是只递归arr[i+1, n]里第k-i大的元素即可;
画外音:这一段非常重要,多读几遍。

这就是随机选择算法randomized_select,RS,其伪代码如下:
int RS(arr, low, high, k){
  if(low== high) return arr[low];
  i= partition(arr, low, high);
  temp= i-low; //数组前半部分元素个数
  if(temp>=k)
      return RS(arr, low, i-1, k); //求前半部分第k大
  else
      return RS(arr, i+1, high, k-i); //求后半部分第k-i大
}

这是一个典型的减治算法,递归内的两个分支,最终只会执行一个,它的时间复杂度是O(n)。

再次强调一下:
  • 分治法,大问题分解为小问题,小问题都要递归各个分支,例如:快速排序
  • 减治法,大问题分解为小问题,小问题只要递归一个分支,例如:二分查找,随机选择

通过随机选择(randomized_select),找到arr[1, n]中第k大的数,再进行一次partition,就能得到TopK的结果。
https://yq.aliyun.com/articles/644716?spm=a2c4e.11153959.0.0.3f0f1047ELmqFI
空间换时间,是算法优化中最常见的手段,如果有相对充裕的内存,可以有更快的算法。
画外音:即使内存不够,也可以水平切分,使用分段的方法来操作,减少每次内存使用量。
TopK问题描述
从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个。
比特位图(bitmap)
bitmap,是空间换时间的典型代表。它是一种,用若干个bit来表示集合的数据结构
例如,集合S={1,3,5,7,9},容易发现,S中所有元素都在1-16之间,于是,可以用16个bit来表示这个集合:存在于集合中的元素,对应bit置1,否则置0。
画外音:究竟需要多少存存储空间,取决于集合中元素的值域,在什么范围之内。
上述集合S,可以用1010101010000000这样一个16bit的bitmap来表示,其中,第1, 3, 5, 7, 9个bit位置是1。
假设TopK的n个元素都是int,且元素之间没有重复,只需要申请2^32个bit,即4G的内存,就能够用bitmap表示这n元素。
扫描一次所有n个元素,以生成bitmap,其时间复杂度是O(n)。生成后,取TopK只需要找到最高位的k个bit即可。算法总时间复杂度也是O(n)。
伪代码为:
bitmap[4G] = make_bitmap(arr[1, n]);
return bitmap[top k bits];
bitmap算法有个缺点,如果集合元素有重复,相同的元素会被去重,假设集合S中有5个1,最终S制作成bitmap后,这5个1只对应1个bit位,相当于4个元素被丢掉了,这样会导致,找到的TopK不准该怎么优化呢?
比特位图计数
优化方法是,每个元素的1个bit变成1个计数。
ae3e22b8f94302a3f515b915aa50a4607e701bcb
如上图所示,TopK的集合经过比特位图计数处理后,会记录每个bit对应在集合S中出现过多少次
接下来,找TopK的过程,就是bitmap从高位的计数开始,往低位的计数扫描,得到count之和等于k,对应的bit就是TopK所求。
25113ecc4910ae219990ae0b2ced381f943772fe
如上图所示,k=5:
(1)第一个非0的count是1,对应的bit是9;
(2)第二个非0的count也是1,对应的bit是8;
(3)第三个非0的count是2,对应的bit是7;
(4)第四个非0的count是2,对应的bit是6,但TopK只缺1个数字了,故只有1个6入选
故,最终的TopK={9, 8, 7, 7, 6}。
结论:通过比特位图精准计数的方式,求解TopK,算法整体只需要不到2次扫描,时间复杂度为O(n),比减治法的随机选择会更快。


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts