关于leetcode215题的一个小问题，java

来源：3-5 三路快排partition思路的应用 Sort Color

v不离不弃v

2020-02-16

波波老师您好，关于leetcode第215题，我有个问题，就是我在进行partition才做的时候，在随机替换arr[l]的时候，为什么在leetcode里面总是显示错误呢？我把那一句注释掉了之后就AC了
我的代码如下，运用了基于快速排序的quick selection方法：

class Solution {
    public int findKthLargest(int[] nums, int k) {
		int n=nums.length;
		return findKthLargest(nums,0,n-1,n-k);
	}
	private static int findKthLargest(int[]arr,int l,int r,int k) {
		if(l==r)
			return arr[l];
		int p=partition(arr,l,r);
		if(p==k)
			return arr[p];
		else if(k<p)
			return findKthLargest(arr,l,p-1,k);
		else
			return findKthLargest(arr,p+1,r,k);
	}
	private static int partition(int[] arr,int l,int r) {
		int j=l;
		//swap(arr,l,(int)(Math.random()*(r-l+1)+1));//这一句删除就AC
		int v=arr[l];
		for(int i=l+1;i<arr.length;i++) {
			if(arr[i]<v)
				swap(arr,++j,i);
		}
		swap(arr,l,j);
		return j;
	}
	private static void swap(int[] arr,int i,int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	
}

写回答

2回答