C solution using heapsort


  • 0
    L
    int* CreateHeap(int* array, int size) {
    	int i=0, n;
    	for (i=0;i<size;i++) {
    		n=i;
    		//if child is at n, parent is at (n-1)/2
    		while (array[n]>array[(n-1)/2]) {
    			int temp=array[n];
    			array[n]=array[(n-1)/2];
    			array[(n-1)/2]=temp;
    			n=(n-1)/2;
    		}
    	}
    	return array;
    }
    
    int HeapSort(int* array, int size, int k) {
    	int i=0,n;
    	for (i=size-1;i>size-k-1;i--) {
    		int temp=array[i];
    		array[i]=array[0];
    		array[0]=temp;
    		n=0;
    		//if parent is at n, children are at 2n+1 and 2n+2
    		while(2*n+1<i) {
    			int index;
    			if (array[2*n+1]>array[2*n+2]) index=2*n+1;
    			else index=2*n+2;
    			if (index==i) index--;
    			if (array[n]<array[index]) {
    				int t=array[n];
    				array[n]=array[index];
    				array[index]=t;
    				n=index;
    			}
    			else break;
    		}
    	}
    	return array[size-k];
    }
    
    int findKthLargest(int* nums, int numsSize, int k) {
        nums=CreateHeap(nums, numsSize);
        return HeapSort(nums, numsSize, k);
    }

Log in to reply
 

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