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

• ``````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.

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

• 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

• "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).