# Partition thinking solution (quick sort) (JAVA)

• ``````public class Solution {
public int findKthLargest(int[] nums, int k) {
//we suppose 1<=k<=nums.length
//so we don't need to check if nums == null
return findK(nums, 0, nums.length - 1, k);
}

public int findK(int[] nums, int head, int tail, int k){
int len = tail - head + 1;
if(len == 1){
}

int i = head, j = tail - 1;
//every time we select nums[tail] to do the partition
//after partition left part < nums[tail], right part >= nums[tail]
while(i <= j){
while(nums[i] <= nums[tail]){
i++;
//all element <= nums[tail]
if(i == tail){
if(k == 1){
return nums[tail];
}
else{
return findK(nums, head, tail- 1, k - 1);
}
}
}
while(nums[j] > nums[tail]){
j--;
//all element > nums[tail]
if(k == len){
return nums[tail];
}
else{
return findK(nums, head, tail - 1, k);
}
}
}
if(i > j){
break;
}
//swap nums[i] and nums[j]
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
i++;
j--;
}
//swap nums[i] and nums[tail]
nums[i] ^= nums[tail];
nums[tail] ^= nums[i];
nums[i] ^= nums[tail];

if(tail - i + 1 == k){
return nums[i];
}
else if(tail - i + 1 < k){
return findK(nums, head, i - 1, k - (tail - i + 1));
}
else{
return findK(nums, i + 1, tail, k);
}
}

}``````

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