LuYouheng @ 2022-12-06 22:52:05
各位大佬,类似计数排序,但是为了节省空间,一个数组元素最多可以对100个数计数。确定了哪一个bottle后再逐个数。 自己测试觉得答案应该对,虽然内存和时间不一定符合要求,但是提交显示两个WA
#include<bits/stdc++.h>
using namespace std;
#define QQ 100
int main()
{
int n,k,empty;
cin>>n>>k;
int a[n],max=0;
for(int i=0; i<n; i++)
{
cin>>a[i];
if(a[i]>max)max=a[i];
}
max /= QQ;
int bottle[max+1]= {0};
for(int i=0; i<n; i++)
{
bottle[ a[i]/QQ ]++;
}
//测试
cout<<"各个瓶子中元素的数量为:";
for(int m=0;m<max+1;m++)
cout<<bottle[m]<<" ";
cout<<endl;
int x=0,count=0,j=0;
while(count<k)
{
count += bottle[j];
j++;
}
j--;
cout<<"第k小的数所在瓶子的ID为"<<j<<endl;
x=count-bottle[j];
k=k-x;
cout<<k<<endl;
int y=0;
for(int i=0; i<n; i++)
{
if(a[i]/QQ==j)
{
if(y==k)
{
cout<<a[i]<<endl;
break;
}
y++;
}
}
/*if(k<n/2){
for(int j=0;j<k;j++){
int min=j;
for(int i=j+1;i<n;i++){
if(a[i]<a[min])
min=i;
}
empty=a[j];
a[j] = a[min];
a[min]=empty;
}
}
else{
k=n-1-k;
for(int j=0;j<k;j++){
int max;
max=j;
for(int i=j+1;i<n;i++){
if(a[i]>a[max])
max=i;
}
empty=a[j];
a[j]=a[max];
a[max]=empty;
}
}
cout<<a[k];
sort(a,a+n);
cout<<a[k];*/
return 0;
}
by LuYouheng @ 2022-12-06 23:17:16
@LuYouheng 上面的代码发现一个问题,就是最后一个bottle里面的数没有排序,烦请帮忙看下面的代码错在哪里:
#include<bits/stdc++.h>
using namespace std;
#define QQ 10
int main()
{
int n,k;
cin>>n>>k;
int a[n],max=0;
for(int i=0; i<n; i++)
{
cin>>a[i];
if(a[i]>max)max=a[i];
}
max /= QQ;
int bottle[max+1]= {0};
for(int i=0; i<n; i++)
{
bottle[ a[i]/QQ ]++;
}
int x=0,count=0,j=0;
while(count<k)
{
count += bottle[j];
j++;
}
j--;
x=count-bottle[j];
k=k-x;
vector<int> b;
for(int i=0; i<n; i++)
{
if(a[i]/QQ==j)
{
b.insert(b.end(),a[i]);
}
}
for(int i=0;i<=k;i++){
int min=i;
for(int j=i+1;j<b.size();j++){
if(b[j]<b[min])min=j;
}
swap(b[min],b[i]);
}
cout<<b[k];
return 0;
}