java solution using MergeSort


  • 0
    S
    class Solution {
        public int findKthLargest(int[] nums, int k) {
            mergesort(nums, 0, nums.length-1);
            return nums[nums.length - k];
        }
        	public void merge(int arr[], int start, int mid, int end) {
    		//size of the two subarrays to be merged
    		int a1 = mid-start+1;
    		int a2 = end-mid;
    		
    		//two arrays
    		int left[] = new int[a1];
    		int right[] = new int[a2];
    		
    		//copy data to temp arrays
    		for (int i=0;i<a1;i++) {
    			left[i]=arr[start+i];
    		}
    		for (int j=0;j<a2;j++) {
    			right[j]=arr[mid+1+j];
    		}
    		
    		//merge
    		int l=0,r=0;
    		int arrIndex = start;
    		while (l<a1 && r<a2) {
    			if(left[l] <= right[r]) {
    				arr[arrIndex] = left[l];
    				l++;
    				//r++;
    			}
    			else {
    				arr[arrIndex] = right[r];
    				//l++;
    				r++;
    			}
    			arrIndex++;
    		}
    		//copy remaining item
    		while (l < a1) {
    			arr[arrIndex] = left[l];
    			l++;
    			arrIndex++;
    		}
    		while (r < a2) {
    			arr[arrIndex] = right[r];
    			r++;
    			arrIndex++;
    		}
    	}
    	public void mergesort(int arr[], int start, int end) {
    		if(start >= end) {
    			return;
    		}
    		else {
    			int mid = (start+end)/2;
    			//left
    			mergesort(arr, start, mid);
    			//right
    			mergesort(arr, mid+1, end);
    			//combine
    			merge(arr, start, mid, end);
    		}
    	}
    }
    
    

Log in to reply
 

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