Accepted C Solution Rt(N*logN) Sp(1) using partition-exchange


  • 0
    R
    int findKthLargest(int* nums, int numsSize, int k) {
    	k=numsSize-k;
        
    	int lo=0;
    	int hi=numsSize-1;
    	while(lo<hi){
    		// partition-exchange 
    		int i=lo+1;
    		int j=hi;
    		while(1){
    
    			while(i<hi && nums[i]<=nums[lo]) ++i;
    			while(j>lo && nums[j]>nums[lo]) --j;
    
    			if(i>=j) break;
    
    			nums[i]^=nums[j];
    			nums[j]^=nums[i];
    			nums[i]^=nums[j];
    		}
    		if(j!=lo){
    			nums[lo]^=nums[j];
    			nums[j]^=nums[lo];
    			nums[lo]^=nums[j];
    		}
    
    		//reduce range
    		if(j>k){
    			hi=j-1;
    		}else if(j<k){
    			lo=j+1;
    		}else{
    			break;
    		}
    	}
    	return nums[k];
    }
    

    well ,it's a classic algorithm.some modification is added to find the kth largest element.


  • 2
    S

    It is a classic algorithm all right, but why do you think its running time is O(nlogn)? Can you prove it?


  • 0
    R

    cause I use the idea of partition-exchange,so the runtime complexity should be the same.wiki said so! http://en.wikipedia.org/wiki/Quicksort#Formal_analysis


  • 0
    S

    "Because I use the idea of partition-exchange,so the runtime complexity should be the same O(nlogn)" This logic does not hold. Partition-exchange itself is an O(N) operation, therefore, a program that uses partition-exchange could take at least O(N) time, but can be also arbitrarily high. So you can't say the running time is O(NlogN) is BECAUSE YOU USE Part-Ex.
    Your program is not O(NlogN), but rather O(N). Think about it: in the 1st iteration, you do part-ex in T(N) time, and reduce the range by half. In the 2nd iteration, you do part-ex only on T(N/2), then reduce the range by another half. So in the end. You program takes T(N) + T(N/2) + T(N/4) + ... = T(2*N), which is O(N).

    Please check the wiki page of 'Quickselect' instead of 'Quicksort'.


  • 0
    R

    yeah,u r right.I didn't think it carefully enough at the first,and it is a Quickselect rather than Quicksort. Much appreciate your constructive answer,I mean that.


Log in to reply
 

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