LeetCode 775. 全局倒置与局部倒置
超时怪 逆序对
class Solution {
typedef long long LL;
public:
bool isIdealPermutation(vector<int>& nums) {
int n = nums.size();
// 局部倒置
int l = 0;
for (int i = 0; i < n - 1; i++) {
if (nums[i] > nums[i + 1]) {
l++;
}
}
// 逆序对:全局倒置
tmp.resize(n);
LL g = merge_sort(nums, 0, n - 1);
return g == l;
}
private:
vector<int> tmp;
LL merge_sort(vector<int> &nums, int l, int r) {
if (l >= r) return 0;
int mid = (l + r) / 2;
LL cnt1 = merge_sort(nums, l, mid);
LL cnt2 = merge_sort(nums, mid + 1, r);
// merge
int i = l, j = mid + 1;
LL cnt = cnt1 + cnt2;
for (int k = l; k <= r; k++) {
if (j > r || i <= mid && nums[i] <= nums[j]) {
tmp[k] = nums[i++];
} else {
tmp[k] = nums[j++];
cnt += mid - i + 1; // 因为前面都已经排完了序,所以可以直接相加中间的数
}
}
for (int k = l; k <= r; k++) nums[k] = tmp[k];
return cnt;
}
};
当然,由于局部逆序就是全局逆序,所以只要判断多一个全局逆序就可以判断是否正确了
class Solution {
public:
bool isIdealPermutation(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
if (abs(nums[i] - i) > 1) return false;
}
return true;
}
};