网站建设2种账号体系,网站建设项目怎么跟进客户,电子商务网站建设与管理试题,设计个网页多少钱每日一道C题#xff1a;
问题#xff1a;给定一个序列a1,a2,…,an#xff0c;如果存在ij并且aiaj#xff0c;那么我们称之为逆序对#xff0c;求逆序对的数目。
要求#xff1a;输入第一行为n,表示序列长度#xff0c;接下来的n行#xff0c;第i1行表示序列中的…每日一道C题
问题给定一个序列a1,a2,…,an如果存在ij并且aiaj那么我们称之为逆序对求逆序对的数目。
要求输入第一行为n,表示序列长度接下来的n行第i1行表示序列中的第i个数输出所有逆序对总数。
暴力解法
思路通过两层循环外层循环遍历序列中的每一个元素内层循环遍历当前元素之后的所有元素。每次内层循环中如果当前外层循环元素大于内层循环元素就找到了一个逆序对计数加1。#include iostream
using namespace std;int main() {int n;cin n;int *arr new int[n];for (int i 0; i n; i) {cin arr[i];}int count 0;for (int i 0; i n - 1; i) {for (int j i 1; j n; j) {if (arr[i] arr[j]) {count;}}}cout count endl;delete[] arr;return 0;
}首先读取序列长度n并动态分配一个大小为n的整数数组arr来存储序列元素。通过一个for循环读取序列中的每一个数并存储到数组中。使用两层嵌套的for循环来统计逆序对。外层循环从0到n - 2内层循环从外层循环变量i的下一个位置到n - 1。如果arr[i] arr[j]则找到一个逆序对count加 1。最后输出逆序对的总数并释放动态分配的数组内存。时间复杂度O(n 2 )因为有两层嵌套循环对于长度为n的序列总的操作次数是12⋯(n−1) n(n−1)/2。
空间复杂度O(n)主要用于存储输入的序列。
归并排序优化解法
思路归并排序是一种分治算法在合并两个有序子数组的过程中可以统计跨越两个子数组的逆序对。将序列不断地分成两半分别对左右两半进行排序然后合并两个有序子数组。在合并过程中如果左边子数组的当前元素大于右边子数组的当前元素那么左边子数组中从当前位置到末尾的所有元素都与右边子数组的当前元素构成逆序对记录逆序对的数量并进行合并操作。#include iostream
using namespace std;// 合并两个有序数组并统计逆序对
long long merge(int arr[], int temp[], int left, int mid, int right) {int i left; // 左子数组的起始索引int j mid 1; // 右子数组的起始索引int k left; // 临时数组的起始索引long long inv_count 0;while (i mid j right) {if (arr[i] arr[j]) {temp[k] arr[i];} else {temp[k] arr[j];inv_count (mid - i 1);}}// 复制左子数组剩余元素while (i mid) {temp[k] arr[i];}// 复制右子数组剩余元素while (j right) {temp[k] arr[j];}// 将临时数组的内容复制回原数组for (i left; i right; i) {arr[i] temp[i];}return inv_count;
}// 归并排序主函数并统计逆序对
long long mergeSort(int arr[], int temp[], int left, int right) {long long inv_count 0;if (left right) {int mid (left right) / 2;// 递归地对左半部分和右半部分进行排序inv_count mergeSort(arr, temp, left, mid);inv_count mergeSort(arr, temp, mid 1, right);// 合并两个有序子数组并统计逆序对inv_count merge(arr, temp, left, mid, right);}return inv_count;
}int main() {int n;cin n;int *arr new int[n];int *temp new int[n];for (int i 0; i n; i) {cin arr[i];}long long result mergeSort(arr, temp, 0, n - 1);cout result endl;delete[] arr;delete[] temp;return 0;
}merge函数用于合并两个有序子数组并统计逆序对。left和right分别是当前要合并的子数组的左右边界mid是中间位置。通过比较左右子数组的元素将较小的元素放入临时数组temp中并统计逆序对。mergeSort函数是归并排序的主函数通过递归地将数组分成两半并排序然后调用merge函数合并并统计逆序对。在main函数中读取序列长度n动态分配两个数组arr和temparr用于存储输入序列temp用于辅助合并操作。读取序列元素后调用mergeSort函数进行排序并统计逆序对最后输出结果并释放内存。时间复杂度O(n log n)因为归并排序每次将数组分成两半共需要(log n)层递归每层递归中合并操作的时间复杂度是O(n)。空间复杂度O(n)主要用于存储临时数组temp。
应用场景拓展
-排序算法稳定性分析逆序对的数量与排序算法的稳定性有关。例如冒泡排序、插入排序等稳定排序算法在排序过程中可以通过计算逆序对的减少来分析其工作过程。对于不稳定排序算法如快速排序了解逆序对的分布有助于优化算法使其在某些情况下更接近稳定排序的效果。
数据相似性度量在数据挖掘和机器学习领域逆序对的概念可以用于衡量两个序列的相似性。如果两个序列的逆序对数量较少说明它们在某种程度上具有相似的顺序结构。例如在推荐系统中可以通过比较用户对不同物品的排序形成序列之间的逆序对数量来判断用户兴趣的相似性进而为用户提供更精准的推荐。算法拓展
树状数组解法可以使用树状数组来解决逆序对问题。树状数组是一种支持高效单点更新和区间查询的数据结构。具体做法是从序列的最后一个元素开始依次将每个元素插入树状数组中并查询当前元素之前小于它的元素个数累加这些个数就得到逆序对的总数。树状数组解法的时间复杂度也是 (O(n \log n))但在某些情况下其实现可能比归并排序更简洁并且可以灵活地支持动态更新序列并重新计算逆序对。#include iostream
#include vector// 树状数组类
class FenwickTree {
private:std::vectorint bit; // 树状数组int n; // 数组大小// 计算lowbitint lowbit(int x) {return x (-x);}public:// 初始化树状数组FenwickTree(int size) : n(size), bit(size 1, 0) {}// 更新操作void update(int idx, int val) {while (idx n) {bit[idx] val;idx lowbit(idx);}}// 查询操作int query(int idx) {int sum 0;while (idx 0) {sum bit[idx];idx - lowbit(idx);}return sum;}
};// 计算逆序对
long long countInversions(const std::vectorint arr) {int n arr.size();// 离散化数组std::vectorint sortedArr arr;std::sort(sortedArr.begin(), sortedArr.end());std::vectorint ranks(n);for (int i 0; i n; i) {ranks[i] std::lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin() 1;}FenwickTree ft(n);long long invCount 0;for (int i n - 1; i 0; --i) {invCount ft.query(ranks[i] - 1);ft.update(ranks[i], 1);}return invCount;
}int main() {int n;std::cin n;std::vectorint arr(n);for (int i 0; i n; i) {std::cin arr[i];}std::cout countInversions(arr) std::endl;return 0;
}FenwickTree 类实现了树状数组的基本操作包括初始化、更新和查询。lowbit 函数用于计算一个数的二进制表示中最低位的 1 及其后面的 0 所构成的数值。countInversions 函数用于计算逆序对。首先对输入数组进行离散化处理将数组中的元素映射到 1 到 n 的范围内以便树状数组处理。然后从数组末尾开始依次将每个元素的排名插入树状数组并查询小于该排名的元素个数累加这些个数得到逆序对的总数。
线段树解法线段树同样可以用于解决逆序对问题。线段树是一种二叉树结构每个节点代表一个区间。通过在线段树中插入元素并查询区间信息可以统计逆序对。线段树的优点在于它能够更灵活地处理区间相关的操作比如在序列动态变化时能够高效地更新逆序对的统计结果。但线段树的实现相对复杂需要对其原理有深入理解。#include iostream
#include vector
#include algorithm// 线段树节点
struct SegmentTreeNode {int left, right;int count;SegmentTreeNode* leftChild;SegmentTreeNode* rightChild;SegmentTreeNode(int l, int r) : left(l), right(r), count(0), leftChild(nullptr), rightChild(nullptr) {}
};// 构建线段树
SegmentTreeNode* buildSegmentTree(int left, int right) {SegmentTreeNode* root new SegmentTreeNode(left, right);if (left right) {int mid (left right) / 2;root-leftChild buildSegmentTree(left, mid);root-rightChild buildSegmentTree(mid 1, right);}return root;
}// 更新线段树
void updateSegmentTree(SegmentTreeNode* root, int idx) {if (root-left root-right) {root-count;return;}int mid (root-left root-right) / 2;if (idx mid) {updateSegmentTree(root-leftChild, idx);} else {updateSegmentTree(root-rightChild, idx);}root-count root-leftChild-count root-rightChild-count;
}// 查询线段树
int querySegmentTree(SegmentTreeNode* root, int left, int right) {if (root-left left root-right right) {return root-count;}int mid (root-left root-right) / 2;if (right mid) {return querySegmentTree(root-leftChild, left, right);} else if (left mid) {return querySegmentTree(root-rightChild, left, right);} else {return querySegmentTree(root-leftChild, left, mid) querySegmentTree(root-rightChild, mid 1, right);}
}// 计算逆序对
long long countInversions(const std::vectorint arr) {int n arr.size();// 离散化数组std::vectorint sortedArr arr;std::sort(sortedArr.begin(), sortedArr.end());std::vectorint ranks(n);for (int i 0; i n; i) {ranks[i] std::lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin();}SegmentTreeNode* root buildSegmentTree(0, n - 1);long long invCount 0;for (int i 0; i n; i) {invCount querySegmentTree(root, ranks[i] 1, n - 1);updateSegmentTree(root, ranks[i]);}return invCount;
}int main() {int n;std::cin n;std::vectorint arr(n);for (int i 0; i n; i) {std::cin arr[i];}std::cout countInversions(arr) std::endl;return 0;
}SegmentTreeNode 结构体定义了线段树的节点每个节点包含区间范围 left 和 right以及该区间内元素的计数 count还有左右子节点指针。buildSegmentTree 函数用于构建线段树递归地将区间划分为左右子区间并创建相应的节点。updateSegmentTree 函数用于更新线段树当插入一个新元素时根据元素的位置更新相应节点的计数。querySegmentTree 函数用于查询线段树中指定区间内的元素计数。countInversions 函数首先对输入数组进行离散化处理然后从数组开头开始依次将每个元素插入线段树并查询大于该元素的元素个数累加这些个数得到逆序对的总数。
