class Solution {
public:
int reversePairs(vector<int>& nums) {
return merge_sort(nums, 0, nums.size() - 1);
}
int merge_sort(vector<int>& q, int l, int r)
{
if(l >= r) return 0;
int mid = l + r >> 1;
int res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
// 归并
int i = l, j = mid + 1;
vector<int> tmp;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp.push_back(q[i++]);
else
{
res += mid - i + 1; // i 后面的都是逆序 因为q[i] 后面的数比q[i]大 同样也比 q[j] 大
tmp.push_back(q[j++]);
}
}
while(i <= mid) tmp.push_back(q[i++]);
while(j <= r) tmp.push_back(q[j++]);
// 赋值回去
for(int i = 0, j = l; i < tmp.size(); i++, j++)
q[j] = tmp[i];
return res;
}
};
方法2：树状数组
树状数组可以用来求:左边/右边比当前元素大/小的个数
怎么做呢 就是拿值当下标，每次出现就给其加1，这样区间查询就可以查到比当前元素大 or 小的和：即出现次数之和
当然了 由于数据可能很大 这里要保序离散化
// 保序离散化
vector<int> alls = nums;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
int find(int x)
{
int l = 0, r = alls.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if(alls[mid] >= x)
r = mid;
else l = mid + 1;
}
return r + 1; // 记得是加1！
}
树状数组的几个操作
class Solution {
public:
int n;
// 离散化
vector<int> tree, alls;
int lowbit(int i)
{
return i & (-i);
}
void update(int i, int val)
{
while(i <= n)
{
tree[i] += val;
i += lowbit(i);
}
}
int query(int i)
{
int sum = 0;
while(i > 0)
{
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
int reversePairs(vector<int>& nums) {
n = nums.size();
tree = vector<int>(n + 10);
// 1. 离散化
alls = nums;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
int res = 0;
for(int x : nums)
{
int y = find(x);
res += query(n) - query(y);
update(y, 1);
}
return res;
}
};
2. 常见的区间问题
区间问题基本都是贪心来搞的 常见的有一下几个
1. 区间合并
按左端点排序 然后遍历区间 如果ed 和新区间的起点分开的话, 就更新合并结果;
看代码就懂了
注意最后可能还剩下一个区间{st, ed} 没有加进去
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
struct Interval{
int l, r;
bool operator<(const Interval& w) const{
return r < w.r;
}
}intervals[N];
int solution()
{
sort(intervals, intervals + n);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i++)
{
int l = intervals[i].l, r = intervals[i].r;
if(ed >= l) continue;
else
{
ed = r;
res += 1;
}
}
return res;
}