K largest elements in the array - various ideas

July 29, 2016

Top k values in the array - review the following article: 

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

1. sorting the array   O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics

7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case

 http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array.  Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...

7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).

7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.

Leetcode 215: Find kth largest element in the array

May 15, 2016

 Problem statement:
 https://leetcode.com/problems/kth-largest-element-in-an-array/

 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

 Read some blogs about this problem:

 http://www.jianshu.com/p/f52a88550588

 Julia likes to spend 10 - 20 minutes to review "Quick Select" - the idea, similar to Quick Sort, most important part is to partition.

 Time complexity: O(nlogn) in quicksort, but O(n) in quick select.

 1. Quick sort: Time complexity: O(nlogn)

 2. Use Heap sort, O(klogN)
Java Solution, using priority queue, code to study:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/215.kth-largest-element-in-an-array.java

Spend 20 minutes to read the blog:  4:23pm - 4:43 pm
1. http://www.cnblogs.com/yuzhangcmu/p/4164807.html

2. https://en.wikipedia.org/wiki/Introselect (read 10 minutes - 4:30pm - 4:40pm)

3. http://stackoverflow.com/questions/7559608/median-of-three-values-strategy

4. http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements

5. http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/ (4:50pm - 5:20pm)

30 minutes to review the solutions, write down short notes:
6 methods:
1. Use bubble k times - O(nk)
Modify bubble sort to run the outer loop at most k times
Like bubble sort, other sorting algorithms like selection sort can also be modified to get the k largest element.

2. Use temporary array
Time complexity: O((n-k)*k)

3. Use sorting
1. Sort the elements in descending order in O(nlogn)
4. Print the first k numbers of the sorted array O(k)
Time complexity: O(nlogn)

4. Use Max Heap
1. Build a Max Heap tree in O(n)
2. Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n+klogn)

5. Use order statistics:
1) use order statistics algorithm to find the kth largest element.
Julia, take some time to review the article: see the topic selection in worst-case linear time O(n). (10 - 15 minutes)
Write down main ideas using your own words:
Use a deterministic algorithm that runs in O(n) in the worst case.

2)