Implement function nth_largest( array, n) and returns the nth largest element


  • 0
    C
    Eg. array = [1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67]  
    
    nth_largest( array, 2) = 55
    
    nth_largest( array, 5) = 9

  • 1
    N

    you can sort the array with merge sort and then get the index directly


  • 1
    M

    You can make the vector into a heap in O(n). You can take from the heap in O(lg n). You have to take k elements to find the k-th largest. Therefore, this can be done in O(n + k lg n) with k < n, which is a lower bound than O(n lg n) (sorting).


  • 1

    C#

    public int nth_Largest(int[] array, int n)
    {
        Array.Sort(array);
        return array[array.Length - n];
    }
    
    

  • 0
    X

    You can apply the idea of quick sort, just pick an element to check if it's the k-th element and then continues to check iteratively.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.