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)
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)
No comments:
Post a Comment