Bestbuy的S8 deal# PDA - 掌中宝
c*i
1 楼
int findKthLargest(vector& nums, int k) {
return findKth(nums, k, 0, nums.size()-1);
}
int findKth(vector& nums, int k, int start, int end)
{
if(start==end)
return nums[start];
int pos = partition(nums, start, end);
int size = pos-start+1;
if(k==size)
return nums[pos];
else if(k>size)
return findKth(nums, k-size, pos+1, end);
else
return findKth(nums, k, start, pos-1);
}
int partition( vector &nums, int start, int end)
{
int mid = start+(end-start)/2;
int pivot = nums[mid];
int i=start, j=end;
while(i<=j)
{
while(ipivot) ++i;
while(j>start && nums[j]
swap(nums[i++], nums[j--]);
}
return i;
}
大家帮我看看我这个partition怎么改？一个简单的case[-1, 2, 0] 就过不了。谢谢！
return findKth(nums, k, 0, nums.size()-1);
}
int findKth(vector
{
if(start==end)
return nums[start];
int pos = partition(nums, start, end);
int size = pos-start+1;
if(k==size)
return nums[pos];
else if(k>size)
return findKth(nums, k-size, pos+1, end);
else
return findKth(nums, k, start, pos-1);
}
int partition( vector
{
int mid = start+(end-start)/2;
int pivot = nums[mid];
int i=start, j=end;
while(i<=j)
{
while(i
while(j>start && nums[j]
swap(nums[i++], nums[j--]);
}
return i;
}
大家帮我看看我这个partition怎么改？一个简单的case[-1, 2, 0] 就过不了。谢谢！
