给定一个数组和一个数num,小于num的数放数组左边,等于num的数放在数组中间,大于num的数放在数组右边 要求:额外空间复杂度O(1),时间复杂度O(n)
#include<bits/stdc++.h>
using namespace std;
void swap(vector<int>& arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
pair<int, int> patition(vector<int>& arr,int l, int r, int aim) {
int less = l - 1;//小于区域
int more = r + 1;//大于区域
while (l < more) {
if (arr[l] < aim) {
swap(arr, ++less, l++);//满足小于,小于区域的下一个和当前值交换,当前值下标往下走一个
}
else if (arr[l] > aim) {
swap(arr, --more, l);//满足大于,大于区域的前一个和当前值交换,之后当前位置的值还需要进行判断,不能移动
}
else {
l++;//等于目标值,当前位置下标往下走
}
}
return make_pair(less++, more - 1);
}
int main() {
int n,aim;
cin >> n >> aim;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
pair<int,int> res = patition(arr,0,n-1,aim);
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}