Describe an O(n)-time algorithm that, given a set S of n distinct numbers and a positive integer k ≤ n, determines the k numbers in S that are closest to the median of S.
solution:
1: procedure k_Closest(S, k) //S: a set of n numbers and k: an integer
2: Output = nothing;
3: m = Select(S, n,n/2) //O(n)
4: for all sin Sand s != m //O(n)
5: s.distance = |m − s|
6: end for
7: md = Select(S.distance, k) //O(n)
8: for all sin S
9: if s.distance<= md.distance then //O(n)
10: Output = Output+ s
11: end if
12: end for
13: return Output
14: end procedure
可见可以在线形时间能得到集合S的K个最邻近点
分享到:
相关推荐
a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the ...
中文名: 算法导论 原名: Introduction to Algorithms 作者: Thomas H. Cormen Ronald L. Rivest Charles E. Leiserson Clifford Stein 资源格式: PDF 版本: 文字版 出版社: The MIT Press书号: 978-0262033848发行...
现代农林英语-转基因植物-Reading-Exercises翻译-.doc
算法导论 CLRS Mit Press - Introduction To Algorithms 2Nd Edition Incl Exercises Edition.chm
麻省理工算法导论 Table of Contents Introduction to Algorithms, Second Edition Preface Part I - Foundations Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started ...
《算法导论》习题解答.rar Solutions for Introduction to algorithms second edition Philip Bille The author of this document takes absolutely no responsibility for the contents. This is merely a vague ...
Exercises-and-Tests-源码.rar
注:下载后,评价时给5星,还你11分 Table of Contents Introduction to Algorithms, Second Edition Preface Part I - Foundations Chapter 1 - The Role of Algorithms in Computing ... List of Exercises
exercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdf
exercises-js-master.rar
算法导论第二版习题答案 英文版 Solutions for Introduction to algorithms second edition Philip Bille The author of this document takes absolutely no responsibility for the contents. This is merely a ...
It is important that you try hard to solve the exercises on your own. Use this document only as a last resort or to check if your instructor got it all wrong. Please note that the document is under ...
a vague suggestion to a solution to some of the exercises posed in the book Introduction to algo- rithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the ...
Solutions_to_Exercises_and_Problems
英文原版 chm 格式 Table of Contents Introduction to Algorithms, Second Edition Preface Part I - Foundations Chapter 1 - The Role of Algorithms in Computing ... List of Exercises
a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the ...
The only way to master matrix algebra is by working through exercises. Most texts have exercises, but few offer solutions. Harville's main text is great because it offers proofs for most theorems. ...
Pandas是入门Python做数据分析所必须要掌握的一个库,本篇精选了十套练习题以及数据文件,帮助读者上手Python代码,完成数据集探索。
ant-exercises-sklearn
Excerpt from Amazon: Some books on algorithms are ... Many new exercises and problems have been added for this edition. As of the third edition, this textbook is published exclusively by the MIT Press.