关注我,分享高质量每日一题题解~
b站同名账号分享力扣杯历届真题视频题解,也欢迎大家提出宝贵意见!
思路:数学
我们希望在调整数组后,保证每一对 $i - a[i]$ 的值均不同,我们将其看作一个数组: $$b[i] = i - a[i]$$ 由于其中的 $i$ 是单调递增的,所以如果我们将 $a[i]$ 变为单调递减,那么整个 $b$ 数组便是单调递增的,一定两两不同。所以我们将原数组由大到小排序即可。
时间复杂度:$O(nlgn)$,对数组进行了排序
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end(), greater<int>());
for(int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
return 0;
}