前两个测试点TLE,后三个AC,大佬帮我看看

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

flowercode @ 2024-03-29 02:30:19

#include<iostream>
using namespace std;
int n,arr[5000005];
void quicksort(int start,int end)
{
   int i=start,j=end,key=arr[(start+end)/2];
   while(i<j)
   {
      while(i<j&&arr[j]>key)
      {
        --j;
      }
      while(i<j&&arr[i]<key)
      {
        ++i;
      }
      swap(arr[i],arr[j]);
   }
   if(n<i)quicksort(start,i-1);
   else if(n>i)quicksort(i+1,end);
   else
   {
   return;
   }
}
int main()
{
   int m;
   scanf("%d%d",&m,&n);
   for(int i=0;i<m;++i)
   {
     scanf("%d",&arr[i]);
   }
   quicksort(0,m-1);
    printf("%d",arr[n]);
}

by Zemu_Ooo @ 2024-03-29 03:55:01

@flowercode

首先没必要把所有数组重排,这样很费时间,而且也没必要,因为你只需要求到第 k 个数,剩下的排序就是无用功。

其次你递归的终止条件有些问题,这个我稍微修改了些。

#include<iostream>
using namespace std;
int n, arr[5000005];

int part(int start, int end, int pi) {
    int pv = arr[pi];
    swap(arr[pi], arr[end]);
    int i = start;
    for (int j = start; j < end; j++) {
        if (arr[j] < pv) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[end]);
    return i;
}

void qs(int start, int end, int k) {
    if (start == end) return;
    int pi = (start + end) / 2;
    pi = part(start, end, pi);
    if (k < pi) qs(start, pi - 1, k);
    else if (k > pi) qs(pi + 1, end, k);
}

int main() {
    int m, k;
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &arr[i]);
    }
    qs(0, m - 1, n);
    printf("%d", arr[n]);
    return 0;
}

by flowercode @ 2024-04-03 21:17:47

@Zemu_Ooo 谢谢大佬!!!


|