Commita1adc15

authored

Update k-th.md

#1215 basics solved.

1 parent46caa5b commita1adc15Copy full SHA for a1adc15

File tree

-1

lines changed

-1

lines changed

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -68,7 +68,7 @@ T order_statistics (std::vector<T> a, unsigned n, unsigned k)`
`68`	`68`
`69`	`69`	`## Notes`
`70`	`70`	`* The randomized algorithm above is named [quickselect](https://en.wikipedia.org/wiki/Quickselect). You should do random shuffle on $A$ before calling it or use a random element as a barrier for it to run properly. There are also deterministic algorithms that solve the specified problem in linear time, such as [median of medians](https://en.wikipedia.org/wiki/Median_of_medians).`
`71`		`-*A deterministic linear solution is implemented in C++ standard library as[std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element).`
	`71`	`+* [std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element) solves this in C++ but gcc's implementation runs in worst case $O(n \log n )$ time.`
`72`	`72`	`* Finding $K$ smallest elements can be reduced to finding $K$-th element with a linear overhead, as they're exactly the elements that are smaller than $K$-th.`
`73`	`73`
`74`	`74`	`## Practice Problems`

Comments

(0)