Qual é a maneira mais rápida de encontrar o késimo maior elemento em uma matriz?

Given my stated mission to not work for linkedin for free, I am going to talk about teachers making students in high school memorize formulas in calculus. Teachers do this because they are lazy and/or want to torture students like they were tortured. Students shouldn't have to memorize formulas for any calculus test, never in reality would they need to spit information like this from memory. As an engineering professor, I would never want my students to rely upon their memory to ensure they have all the correct variables and relationship. Indeed, give them all the formulas in the book, the real challenge in actual engineering is knowing which formulas to apply and when. Teachers make students hate math by making such ridiculous demands.

Consider using the QuickSelect algorithm. This algorithm is a variant of QuickSort and provides an average-case time complexity of O(n), making it faster than sorting the entire array. QuickSelect strategically partitions the array, reducing the search space by half in each iteration. By selecting the appropriate pivot element, it efficiently converges toward the kth largest element.

Sorting is the most intuitive approach towards solving this problem. It is the natural tendency of how a person would solve this problem given a pen and a paper. Sorting an array of size n would lead to the time complexity of O(n*log(n)) and this can be improved as we will see in the next part.

Discovering the Kth largest element in an array typically involves sorting the elements and identifying the Kth largest. This method carries a time complexity of O(n log n) and occupies space at O(n) or O(log n) depending on the programming language utilized.

It is an easy and clear way to do the job. It will make your code readable. In my experience, if you write code for local use it is a solution. However, be aware that there are faster ways to get kth largest element.

Heap would be a much more efficient way to solve this problem. To find the kth largest element in an array, we would need a min heap of a fixed size k. While traversing the array we would keep on inserting the elements in our heap and as soon as the heap size passes k, we would pop the elements. This makes sure that smaller elements (since we have a min heap) are removed. At the end of traversal, we would have the kth largest element on the top of the heap. This solution is much more efficient with time complexity of O(n*log(k)) if n is the array size. But introduces a O(k) space complexity.

To find the kth largest number in an array using a heap, you can follow these steps: 1. Build a min-heap of size k with the first k elements of the array. 2. For each remaining element in the array (starting from index k), compare it with the root of the min-heap. 3. If the current element is greater than the root of the min-heap, replace the root with the current element and perform heapify to maintain the min-heap property. 4. After processing all elements in the array, the root of the min-heap will be the kth largest number. This implementation has a time complexity of O(nlogk), where n is the size of the array and k is the parameter determining the kth largest number.

Do this in a while loop, iteratively! Do not use recursion and put the entire array on the stack at each recursive call, that's a horrible way to implement it. Use a while loop, and an if else ladder at the end of it for i < k, i > k and i == k (return). Quickselect is the optimal, the way to avoid the worst case, i.e choosing a bad pivot is to randomly select the pivot index at each iteration, instead of mid. Also ensure that the input array does not meet any special conditions such as being reverse sorted or something like that which would lead to very long runtimes and ultimately hit the upper bound for time complexity.