算法----中位数算法的妙用(更新中) - L.J.SHOU的专栏 - 博客频道 - CSDN.NET


算法----中位数算法的妙用(更新中) - L.J.SHOU的专栏 - 博客频道 - CSDN.NET

中位数算法O(N)有许多妙用,能够在一些场合下替代 排序O(NlgN)

1. 中位数算法

求N个数组中的中位数即求第n/2大的数

算法导论中给出了两种求第k大的数的算法

算法1: 随机算法 平均复杂度O(n)

思路:利用quicksort的随机版本的partition, 将数组分成2部分:

         if 左边部分数目<k, 则在右边递归搜索

         else if 左边的数> k, 则在左边递归搜索

          else  return a[partition];

算法2: 确定性算法 最坏复杂度O(n)


2. 三个例子

例题1:带权中位数

n个数x[1], x[2],..., x[n], 各自带有一个权重, w[1], w[2], ..., w[n], w的总和是1

求x[k]满足 所有满足x[i] < x[k]的元素的权重之和< 1/2, 所有满足x[i] > x[k]的元素的权重之和 >=1/2;


算法1: 先排序O(NlgN), 从前往后遍历数组,找到第一个x[k], 使得前k个元素的权重之和>=1/2, return x[k]

算法2: 分治: 用中位数算法,将问题的规模减半

思路: 其实这个题并不需要排序,我们仅仅需要找到 n个数中较小的K(未知)个数的集合,使得它的和<1/2, 其他元素的和>=1/2, 具体这两个集合中的数并不需要排序。考虑用中位数算法来找这个集合。

伪代码:   WeightedMid(a, i, j,  w)

                    mid = Select(a, i, j) //中位数算法

                    left_sum = w[i]+w[i+1]+...+w[mid-1]; //左半部分数组的权重和

                    right_sum = w[mid+1]+w[mid+1]+...w[j];

                    if left_sum >=w,  return WeightedMid(a, i, mid-1, w);

                    elseif right_sum >w, return WeightedMid(a, mid, j, w-left_sum);

                    else  return x[mid];

T(n) = T(n/2) + O(n)   


例题2: 部分背包问题:

一个窃贼去一家商店偷窃,有n件商品: 第i件物品值vi元,重wi榜(vi, wi都是整数),他的背包最多只能装下W榜物品,

每件商品他可以选择一部分带走,而不像0-1背包问题。问他最多能带走多贵的物品?


分析: 由于部分背包问题允许仅拿走物品的一部分,物件更像是金粉,可证明其具有贪心的性质。

算法1: 贪心

按照每榜的价值进行排序,然后由价值的大小依次往包里装,直到重量为W。

算法复杂度是 O(nlgn).


能不能将其复杂度降低到线性呢?

注意到,无论是动态规划还是贪心,其实都具有问题可分(decomposed)的性质, 也就是可以考虑用分治(divide-and-conquer)。

要构造O(n)的算法,首先想到 T(n) = T(n/2) + O(n),

--------------- 在O(n)的时间内把问题的规模降为一半,那么就得到了一个O(N)的算法。

分析:

贪心算法时间复杂度主要是排序,可以不排序吗?

  可以。排序只是为了找出那些单价高的物品集合,所以我们并不需要把所有的单价进行排序

我们只需要找到背包所能装得下的那部分单价较高的物品即可。这类似于在数组中找前k大的k个数(复杂度是O(N)).

因此使用排序我们其实做了多余的比较。

目标:一分为二,而且要找的是前k大的k个数(k未知),

Bingo! 先找出中位数!


算法2:

n个物品的单价数组: A[1:n]

找出其中位数,将数组分成3个部分: A{单价高于中位数}   B{单价等于中位数}  C{单价小于中位数}

注意到 {A}, {A+B}, {C}的规模<=n/2

下面分三种情况:

1. 若集合A中的物品总质量 >= W, 递归在A中解部分背包问题

2. 若集合A中的物品总质量 < W, 且集合{A+B}中的物品总质量 >=W,  将A中物品全部装入包中,剩余的从B中随便取即可

3. 若集合{A+B}中的物品总质量 < W, 将A和B中的物品全部放入背包中,剩余的质量递归地在集合C中求解

复杂度分析:

求中位数复杂度是 O(N), 上述三种情况中除了子问题外,也顶多花O(N)时间,

T(n) <= T(n/2) + O(n)

所以 T(n) = O(n)


例3:

N个数中有一个数出现的次数大于1/2

算法1: 先排序,再扫描一次数组,记录出现的次数 O(nlgn)

算法2: 这一问题其实也不需要排序。中位数即为所求。O(n)


Read full article from 算法----中位数算法的妙用(更新中) - L.J.SHOU的专栏 - 博客频道 - CSDN.NET

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