用了一个类似计数排序的办法,烦请大佬帮着找找错误出在哪

P1923 【深基9.例4】求第 k 小的数

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;
}

|