求解一个令我迷惑的小问题,回复必关
查看原帖
求解一个令我迷惑的小问题,回复必关
1478175
shibazhichang18楼主2024/12/8 15:18

这是我看了题解后尝试写的代码,听取WA声一片

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
int a[N] , k;
void qsort(int l , int r)
{
	int mid = l + (r - l) / 2;
	int i = l , j = r;//l和r需要保留
	while(i <= j)
	{
		while(a[j] > a[mid])
			j --;
		while(a[i] < a[mid])
			i ++;
		if(i <= j)
		{
			swap(a[i] , a[j]);
			i ++;
			j --;
		}
	}
	//快排后数组被划分为三块: l<=j<=i<=r
	if(k <= j)
		qsort(l , j);//递归 
	else if(k >= i)
		qsort(i , r);
	else
	{
		printf("%d" , a[j + 1]);
		exit(0);
	}
}
int main()
{
	int n;
	scanf("%d %d" , &n , &k);//注意地址符 
	for(int i = 0;i < n;i ++)
		scanf("%d" , &a[i]);
	qsort(0 , n - 1);
    return 0;
}

然而当我把快排部分修改成这样,就神奇地AC了...

//其他部分都一样,就省略了
	int mid = a[l + (r - l) / 2];
	int i = l , j = r;//l和r需要保留
	while(i <= j)
	{
		while(a[j] > mid)
			j --;
		while(a[i] < mid)
			i ++;

不是,这俩有什么本质上的区别吗??恳请大佬解答!

2024/12/8 15:18
加载中...