寻找最大的k个数 - 编程之美2.5


http://blog.csdn.net/insistgogo/article/details/7689297
题目描述:输入n个整数,输出其中最大的k个。
举例:输入序列1、2、3、4、5、6、7、8,输出最大的4个数字为5、6、7、8。


方法三:不对前K个数进行排序 + 不对N-k个数排序,可以使用
思路:寻找第K个大元素。
具体方法:使用类似快速排序,执行一次快速排序后,每次只选择一部分继续执行快速排序,直到找到第K个大元素为止,此时这个元素在数组位置后面的元素即所求
  1. 在数组S中^^随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。  
  2. 这时有两种情况:  
  3.     1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;  
  4.     2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。

方法七、我们要尽可能少的遍历所有数据。相比下,属于较好的算法,提倡使用
思路:维护一个大小为k的小根堆,堆顶元素是最大K 个数中最小的一个,即第K个元素
  1. 处理过程对于数组中的每一个元素X,判断与堆顶的大小  
  2.     如果X 比堆顶小,则不需要改变原来的堆  
  3.         因为这个元素比最大的K 个 数小。  
  4.     如果X比堆顶大,要用X 替换堆顶的元素Y 。  
  5.         调整堆的时间复杂度为O(log2K)。  
时间复杂度: O (N * log2 K ),算法只需要扫描所有的数据一次
空间复杂度:大小为K的数组,只需要存储一个容量为K 的堆。
注意、大多数情况下,堆可以全部载入内存。如果K 仍然很大,我们可以尝试先找最大的K ’个元素,然后找第K ’+1个到第2 * K ’ 
元素,如此类推(其中容量K ’的堆可以完全载入内存)。这时,每求出K’个数,就遍历一遍数据了

方法八、可以直接对原数组建立大根堆,取这个优先队列前k个值。数据量小的时候可以考虑
思路:在线性时间内,能将一个无序的数组建成一个最小堆,然后取堆中的前k个数
建堆时间是O(n),每次调整时间为O(log n)
复杂度O(n)+k*O(log n)
在有优化,每次调整时不需要调整logn次了,只需调整K次,这个k 和 取第k个数是同一个数
也就是,建堆后,直接取出第一个最大值。取第一个最大值后,大根堆已经被破坏了,之后需要向下进行k次调整就好。取第2个最大值后,之后进行k-1次调整,等等。注意,每次取完值后,这个堆就不是大根堆了
原来堆的方法,每次调整l最大是logn次,调整后仍是大根堆
优化后的时间复杂度是O(n+k^2)
评价:这两个方法的时间复杂度都比维护一个大小为k的小根堆的方法好,但是后者是空间复杂度还是很好的,内存中只需维护一个大小为k堆,而其他两个方法需要把整个堆都放入内存,这对于处理海量数据效率还是不是很好啊,而且作者July还在程序验证过,其实这两种算法在时间上区别不是很大。

思路1:寻找第K个大的元素 + 计数排序 + 数组实现
具体方法:使用计数排序,另开辟一个数组,记录每个整数出现的次数,然后再从大到小取最大的 K 个。
缺点:
1、有些数没有出现过,仍要为其保留一个空间,空间浪费比较严重
2、不能处理浮点数
思路2:寻找第K个大的元素 + 计数排序 + map实现
具体方法:利用STL最后的map保存每一个元素Si出现的次数,之后从大到小扫描找到K个数
时间复杂度O(n*logn)     空间复杂度O(n)
注意:
1、可以处理浮点数 

方法五、基数排序,不提倡使用
思路:寻找第K个大的元素 + 基数排序
时间复杂度:O ( (N +M )* log2 M (|V max - V min |/delta) )
  1. 一次遍历,找到最大的数为Vmax ,最小的数为Vmin  
  2. 对区间[V min , V max ]分成M 块  
  3.     每个小区间的跨度为d =(V max – V min )/M   
  4.     即 [V min , V min +d ], [V min + d , V min + 2d ],……   
  5. 扫描一遍所有元素,统计各个小区间中的元素个数,我们可以知道第K大的元素在哪一个小区间。  
  6. 然后,再对那个小区间,继续进行分块 处理。  
  7. 。。。。递归下去,一直找到一个区间只含第K个数为止  
方法六、类二分查找,不提倡使用
思路:寻找第K个大的元素 + 类二分查找
1、delta的取值要比任意两个不相等的元素差值之最小值小。如果所有元素都是整数,delta可以取值0.5。
2、算法的时间复杂度O( N * log2 (|Vmax - Vmin| /delta) ) 
  1. while(Vmax – Vmin > delta)  
  2. {  
  3.     Vmid = Vmin + (Vmax - Vmin) * 0.5;  
  4.     if(f(arr,N,Vmid) >= K)  
  5.         Vmin = Vmid;  
  6.     else  
  7.         Vmax = Vmid;  
  8. }  
  9. 伪码中f(arr ,N,Vmid)返回数组arr [0, …, N-1]中大于等于Vmid的数的个数。 

方法一:对所有元素进行排序,之后取出前K个元素,不提倡使用
思路:使用最快排序算法,选择快排 或 堆排
时间复杂度:O(n*logn) + O(K) = O(n*logn)
特点:需要对全部元素进行排序,K = 1 时,时间复杂度也为O(n*logn)
方法二:只需要对前K个元素排序,不需要对N-K个元素进行排序,不提倡使用
思路:使用 选择排序 或 起泡排序,进行K次选择,可得到第k大的数时间复杂度:O(n*k)

http://blog.csdn.net/v_july_v/article/details/6370650

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