BM20. [数组中的逆序对]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM20. 数组中的逆序对
题目的主要信息:
- 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。
- 输入一个数组,求一个数组的全部逆序对,答案对1000000007取模
- 要求:空间复杂度,时间复杂度
- 保证输入的数组中没有的相同的数字
方法一:归并排序
具体做法:
因为我们在归并排序过程中会将数组划分成最小2个元素的子数组,然后依次比较子数组的长度,这里我们也可以用相同的方法统计逆序对。我们主要有三个阶段:
- 划分阶段:将待划分区间从中点划分成两部分;
- 排序阶段:使用归并排序递归地处理子序列,同时统计逆序对;
- 合并阶段:将排好序的子序列合并。
因为在归并排序中,右边大于左边时,它大于了左边的所有子序列,基于这个性质我们可以不用每次加1来统计,减少运算次数。
class Solution { public: int mod = 1000000007; int mergeSort(int left, int right, vector<int>& data, vector<int>& temp){ if (left >= right) // 停止划分 return 0; int mid = (left + right) / 2; //取中间 int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); //左右划分 res %= mod; //防止溢出 int i = left, j = mid + 1; for (int k = left; k <= right; k++) temp[k] = data[k]; for (int k = left; k <= right; k++) { if (i == mid + 1) data[k] = temp[j++]; else if (j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; else { //左边比右边大,答案增加 data[k] = temp[j++]; res += mid - i + 1; // 统计逆序对 } } return res % mod; } int InversePairs(vector<int> data) { int n = data.size(); vector<int> res(n); return mergeSort(0, n - 1, data, res); } };
复杂度分析:
- 时间复杂度:,归并排序利用分治思想,复杂度为这个
- 空间复杂度:,辅助数组temp长度为及递归栈最大深度不会超过
方法二:树状数组
具体做法:
树状数组是如图所示的数组,它可以累加前缀和。
比如4统计123的前缀和,8统计1234567的前缀,而且因为是树状的,因此操作都是。
我们首先对原数组进行离散化操作,经过排序后的操作加上后续二分查找映射,将 数组[1 5000 2 400 30] 映射为 ——> [1 5 2 4 3],即使他们相连,减少空间需求,因为题目所给没有重复元素,因此也不用去重,还是个数字。
然后从前往后遍历每个元素,查找在树状数组中的前缀和,表示这个元素在树状数组中出现过多少,前缀和做差,,表示值在中出现的次数,也就是逆序数个数。
class BIT { private: vector<int> tree; int n; public: BIT(int m) : n(m), tree(m + 1) {} //初始化 int lowbit(int x){ //使数组呈现2、4、8、16这种树状 return x & (-x); } int query(int x){ //查询序列1到x的前缀和 int res = 0; while(x){ res += tree[x]; x -= lowbit(x); } return res; } void update(int x){ //序列x位置的数加1 while(x <= n){ tree[x]++; x += lowbit(x); } } }; class Solution { public: int mod = 1000000007; int InversePairs(vector<int> data) { int n = data.size(); int res = 0; vector<int> temp = data; //离散化 sort(temp.begin(), temp.end()); //排序 for(int i = 0; i < n; i++) //二分法重新映射 data[i] = lower_bound(temp.begin(), temp.end(), data[i]) - temp.begin() + 1; BIT bit(n); //建立树状数组 for(int i = 0; i < n; i++){ //统计逆序对 res = (res + bit.query(n) - bit.query(data[i])) % mod; bit.update(data[i]); } return res; } };
复杂度分析:
- 时间复杂度:,sort函数排序为,离散化过程中二分法时间复杂度为,一共次,统计逆序对过程中,查询更新都是,一共次
- 空间复杂度:,辅助数组temp的长度和树状数组的长度都是