三路快排最后一个TLE了0.07s,求助
查看原帖
三路快排最后一个TLE了0.07s,求助
1454742
MikanseIA楼主2024/11/18 20:57
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void swap(int arr[] , int x , int y) {
  int t = arr[x]; arr[x] = arr[y]; arr[y] = t;
}
void sort(int arr[] , int left , int right) {
  if(right <= left) return;
  int lt = left + 1, gt = right , i = left + 1;
  int random_index = left + rand() % (right - left + 1);
  swap(arr,left,random_index);
  int pivot = arr[left];/*lt = less than gt = greater than*/
  while(i <= gt) {
    if(arr[i] == pivot) i++;
    else if(arr[i] > pivot) {
      swap(arr,gt,i); gt--;
    }
    else {
      swap(arr,lt,i); lt++; i++;
    }
  }
  swap(arr,left,lt - 1);
  sort(arr,left,lt - 2); sort(arr,gt + 1,right);
}
int main() {
  int n,k; int *nums;
  scanf("%d%d",&n,&k);
  nums = (int*)malloc(sizeof(int) * n);
  for(int i = 0 ; i < n ; i++) scanf("%d",&nums[i]);
  sort(nums,0,n - 1);
  printf("%d",nums[k]);
  free(nums);
}
2024/11/18 20:57
加载中...