代码疑问

Question

#include<iostream>

#include<algorithm>

#include<cassert>

using namespace std;

int arr[100];

int partition(int arr[],int l,int r)

{   if(l>=r)

return 0; 

int v=arr[l];

int j=l,i=r;

while(j<i)

{

while(j<i&&arr[j]<v)

j++;

if(j<i)

{

arr[j]=arr[i];

i--;

}

while(j<i&&arr[i]>=v)

i--;

if(j<i)

{

arr[j]=arr[i];

j++;

}

}

return j;

}

int selection(int arr[],int l,int r,int k)

{

if(l==r)

return arr[l];

int p=partition(arr,l,r);

if(k==p)

return arr[p];

else if(k<p)

return selection(arr,l,p-1,k);

else

return selection(arr,p+1,r,k);

}

int main()

{

int n,i,k,c;

cin>>n;

int arr[n];

cin>>k;

for(i=0;i<n;i++)

cin>>arr[i];

c=selection(arr,0,n-1,k);

cout<<c<<endl;

return 0;

}

其他部分相同，只在main()函数部分有所改动，为什么不能得到正确的第n大的结果呢？

代码有疑问

Answer 1

liuyubobobo 2017-10-31 11:42:11

1. 请确认算法代码是我的代码逻辑一致：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-05-Selection/main.cpp

2. 注意，在这个代码中，k是从0开始计算的。也就是最小值k=0；第二小值k=1；...依次类推

3. 如果确认了1，2点的话，具体是什么测试用例不能正确获得结果了呢？

• 提问者 weibo_瘦不下来的胖胖儿_0 #1

  6
  3
  1 2 3 4 5 6
  6
  
  6
  2
  6 5 4 3 2 1
  4
  
  7
  3
  7 8 2 1 4 5 6
  1
  思路是一样的啊，除了最后部分main函数不同，除了k的问题，感觉数组没有进行排序，不知道是不是我的main函数没有写对。

• liuyubobobo 回复 提问者 weibo_瘦不下来的胖胖儿_0 #2

  这个算法本身没有对数组进行排序，只是部分排序，最终应该可以返回正确的结果。

• 提问者 weibo_瘦不下来的胖胖儿_0 回复 liuyubobobo #3

  不行的。。不知道哪里有问题，测试用力几乎很少有正确的

点开查看后面1条评论