Preface :
A application might need to find the median value in an array. The median is a value M such that half the array elements are <= M and remaining values are >= M. For instance, the Bureau of Labor Statistics reports the median family income as the middle value in a random sample of family incomes. Finding a median is a special case of a more general problem that locates the kth-largest element of an array. Out destination "kth largest" implies that value at index k. The 0th largest element is thus the smallest element. We can solve the problem of finding the kth-largest element by first sorting the array and then simply accessing the element at position k. This is an inefficient algorithm, however, because the sort requires additional work to order all of the elements. We simply need to locate the position of the kth-largest value in the list by partitioning the elements into two disjoint sublists. The lower sublist must contain k elements that are less than or equal to kth Largest, and the upper sublist must contains elements that are greater than or equal to kth Largest. Below figure illustrates the partition. The elements in the lower sublist do not need to be ordered only have values that are less than or equal to kth Largest. The opposite condition applies to the upper sublist :
Method findKth() :
We will apply the "pivoting" technique from the quicksort algorithm to create the partition. The method findKth() takes an array arr, the indices for the index range [first, last), and the position k as arguments. It modifies the array so that the kth largest element is at index k. The work is done by calling pivotIndex() from within the recursive method findKth(). Each call to findKth() takes the array and an index range and has pivotIndex() rearrange elements greater than or equal to the pivot value. If the index is k, then the pivot is the kth-largest element, and the method findKth() return because it has reached the stopping condition. If the index is greater than k, then a recursive call to findKth() with index range [first, index) continues the search for kth largest element in the lower sublist. Otherwise, a recursive call to findKth() with index range [index+1, last) continues the search in the upper sublist :
Running Time of findKth() :
This algorithm should have a faster running time than quicksort, because it rejects either the lower or upper sublist at each stage. Let us intuitively develop its running time for an n-element array. Assume, as we did for quicksort, that the pivot always lies at the midpoint of the sublist. Under this assumption, locating the first pivot requires approximately n comparisons, finding the second pivot requires approximately n/2 comparisons and so on. The whole process requires no more than :
n + n/2 + n/4 + n/8 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...) = 2n
This intuitive argument indicates that the average running time for findKth() is O(n), which is linear. If the pivot is always the largest of smallest element int its sublist, findKth() has the same worst-case running time as quicksort, which is O(n^2).
This is a blog to track what I had learned and share knowledge with all who can take advantage of them
標籤
- [ 英文學習 ]
- [ 計算機概論 ]
- [ 深入雲計算 ]
- [ 雜七雜八 ]
- [ Algorithm in Java ]
- [ Data Structures with Java ]
- [ IR Class ]
- [ Java 文章收集 ]
- [ Java 代碼範本 ]
- [ Java 套件 ]
- [ JVM 應用 ]
- [ LFD Note ]
- [ MangoDB ]
- [ Math CC ]
- [ MongoDB ]
- [ MySQL 小學堂 ]
- [ Python 考題 ]
- [ Python 常見問題 ]
- [ Python 範例代碼 ]
- [心得扎記]
- [網路教學]
- [C 常見考題]
- [C 範例代碼]
- [C/C++ 範例代碼]
- [Intro Alg]
- [Java 代碼範本]
- [Java 套件]
- [Linux 小技巧]
- [Linux 小學堂]
- [Linux 命令]
- [ML In Action]
- [ML]
- [MLP]
- [Postgres]
- [Python 學習筆記]
- [Quick Python]
- [Software Engineering]
- [The python tutorial]
- 工具收集
- 設計模式
- 資料結構
- ActiveMQ In Action
- AI
- Algorithm
- Android
- Ansible
- AWS
- Big Data 研究
- C/C++
- C++
- CCDH
- CI/CD
- Coursera
- Database
- DB
- Design Pattern
- Device Driver Programming
- Docker
- Docker 工具
- Docker Practice
- Eclipse
- English Writing
- ExtJS 3.x
- FP
- Fraud Prevention
- FreeBSD
- GCC
- Git
- Git Pro
- GNU
- Golang
- Gradle
- Groovy
- Hadoop
- Hadoop. Hadoop Ecosystem
- Java
- Java Framework
- Java UI
- JavaIDE
- JavaScript
- Jenkins
- JFreeChart
- Kaggle
- Kali/Metasploit
- Keras
- KVM
- Learn Spark
- LeetCode
- Linux
- Lucene
- Math
- ML
- ML Udemy
- Mockito
- MPI
- Nachos
- Network
- NLP
- node js
- OO
- OpenCL
- OpenMP
- OSC
- OSGi
- Pandas
- Perl
- PostgreSQL
- Py DS
- Python
- Python 自製工具
- Python Std Library
- Python tools
- QEMU
- R
- Real Python
- RIA
- RTC
- Ruby
- Ruby Packages
- Scala
- ScalaIA
- SQLAlchemy
- TensorFlow
- Tools
- UML
- Unix
- Verilog
- Vmware
- Windows 技巧
- wxPython
訂閱:
張貼留言 (Atom)
[Git 常見問題] error: The following untracked working tree files would be overwritten by merge
Source From Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 # git clean -d -fx 方案2: 今天在服务器上 gi...
-
前言 : 為什麼程序管理這麼重要呢?這是因為: * 首先,本章一開始就談到的,我們在操作系統時的各項工作其實都是經過某個 PID 來達成的 (包括你的 bash 環境), 因此,能不能進行某項工作,就與該程序的權限有關了。 * 再來,如果您的 Linux 系統是個...
-
屬性 : 系統相關 - 檔案與目錄 語法 : du [參數] [檔案] 參數 | 功能 -a | 顯示目錄中個別檔案的大小 -b | 以bytes為單位顯示 -c | 顯示個別檔案大小與總和 -D | 顯示符號鏈結的來源檔大小 -h | Hum...
-
來源自 這裡 說明 : split 是 Perl 中非常有用的函式之一,它可以將一個字串分割並將之置於陣列中。若無特別的指定,該函式亦使用 RE 與 $_ 變數 語法 : * split /PATTERN/,EXPR,LIMIT * split /...
沒有留言:
張貼留言