544.Top k Largest Numbers

1.Description(Medium)

Given an integer array, find the top_k_largest numbers in it.

Example

Given[3,10,1000,-99,4,100]andk=3. Return[1000, 100, 10].

2.Code

Quick sort then create a new array to store them.

public int[] topk(int[] nums, int k) {

        quickSort(nums,0,nums.length-1);

        int[] topk=new int[k];

        for(int i=0;i<k && i<nums.length;i++){
            topk[i]=nums[i];
        }

        return topk;             
    }

    //descending the quick sort
    public static int partition(int[] arr,int left,int right)
    {
        int i=left;
        int j=right;
        int temp;
        int pivot= arr[(left+right)/2];


        while(i<=j)
        {
            while(arr[i]>pivot)
                i++;
            while(arr[j]<pivot)
                j--;

            if(i<=j)
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                i++;
                j--;
            }
        }

        return i;

    }

    //descending
    public static void quickSort(int[] arr,int left,int right)
    {
        int index=partition(arr,left,right);

        if(left<index-1)
        {
            quickSort(arr,left,index-1);
        }
        if(right>index)
        {
            quickSort(arr,index,right);
        }
    }