# Java QuickSelect Solution

• ``````public class Solution {
public int findKthLargest(int[] nums, int k) {
return findKthLargestRec(nums, 0, nums.length-1, k);
}

private int findKthLargestRec(int[] nums, int start, int end, int k) {
int pIdx = partition(nums,start,end);
if(k-1<pIdx)
return findKthLargestRec(nums,start,pIdx-1,k);
else if(k-1>pIdx)
return findKthLargestRec(nums,pIdx+1,end,k);
else
return nums[k-1];
}

private int partition(int[] nums, int start, int end) {
int pVal = nums[start]; // use random can save time in average
swap(nums,start,end);
int lo = start; int hi = end-1;
while(lo<=hi) {
while(lo<=end-1 && nums[lo]>pVal) {lo++;}
while(hi>=start && nums[hi]<=pVal) {hi--;}
if(lo<=hi)
swap(nums,lo++,hi--);
}
swap(nums,lo,end);
return lo;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}``````

• ``````public class Solution {
public int findKthLargest(int[] nums, int k) {
return findKthLargestRec(nums, 0, nums.length-1, k);
}

private int findKthLargestRec(int[] nums, int start, int end, int k) {
int pIdx = partition(nums,start,end);
if(k-1<pIdx)
return findKthLargestRec(nums,start,pIdx-1,k);
else if(k-1>pIdx)
return findKthLargestRec(nums,pIdx+1,end,k);
else
return nums[k-1];
}

private int partition(int[] nums, int start, int end) {
int pVal = nums[start]; // use random can save time in average
swap(nums,start,end);
int lo = start; int hi = end-1;
while(lo<=hi) {
while(lo<=end-1 && nums[lo]>pVal) {lo++;}
while(hi>=start && nums[hi]<=pVal) {hi--;}
if(lo<=hi)
swap(nums,lo++,hi--);
System.out.println("SWAP");
for(int l = start; l <= end-1; l++)
System.out.print(nums[l] + ",");
System.out.println();
}
swap(nums,lo,end);
System.out.println("LAST SWAP");
System.out.print("lo: " + lo);
System.out.println();
for(int l = start; l <= end-1; l++)
System.out.print(nums[l] + ",");
System.out.println();
return lo;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````

Please run this code. I don't think your partition is right because you write 【nums[hi]<=pVal】, though the result is right.

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