问题描述:若一个数组为[A1, A2, ..., An],若有i<j且Aj>Ai,那么Ai和Aj就构成一个逆序对。该问题是求出数组中所有逆序对的数目。
算法思想:使用分治法可以在O(nlogn)的时间复杂度下,求出逆序对。其思想为,把一个数组拆分为两个子数组,不妨称为L和R,那么原数组的逆序对数就等于L的逆序对数加上R的逆序对数,再加上一个元素在L中另一个元素在R中构成的逆序对数。可以在分解时独立求出L和R中逆序对数,然后合并时再加上L和R共同构成的逆序对数。
public class reverseOrder {
private static int number = 0;
public static void mergeSort(int[] a, int[] b, int begin, int end) {
if (begin < end) {
int mid = (begin + end) / 2;
mergeSort(a, b, begin, mid);
mergeSort(a, b, mid+1, end);
merge(a, b, begin, mid, end);
copy(a, b, begin, end);
}
}
public static void merge(int[] a, int[] b, int begin, int mid, int end) {
int i = begin;
int k = begin;
int j = mid+1;
while (i <= mid && j <= end) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
}
else {
b[k++] = a[j++];
number += mid - i + 1;
}
}
while (i <= mid)
b[k++] = a[i++];
while (j <= end)
b[k++] = a[j++];
}
public static void copy(int[] a, int[] b, int begin, int end) {
for(int i = begin; i <= end; i++)
a[i] = b[i];
}
public static void main(String[] args) {
int[] a = {5, 1, 2, 3, 4};
int[] b = new int[5];
split(a, b, 0, 4);
System.out.println("The number of reverse pair is: " + number);
}
}
分享到:
相关推荐
这段代码中,逆序对的计算是在归并过程中完成的,这使得算法的时间复杂度达到 O(NlogN),满足了题目的要求。注意,`mergeSort()` 的递归调用可能会导致栈空间的消耗,但在这个特定的实现中,由于每次分割的子区间是...
在`POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】.cpp`文件中,你应该能够找到使用归并排序算法计算逆序对的实现。这种方法相比于直接求解,虽然增加了额外的排序操作,但大大提高了时间效率,尤其在处理大...
请考虑一个最坏情况O nlogn 的算法确定n个元素的逆序对数目 注意此题请勿用O n^2 的简单枚举去实现 输入格式 第一行:n 表示接下来要输入n个元素 n不超过10000 第二行:n个元素序列 输出格式 逆序对的个数 ...
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。 一个n个元素序列的逆序对个数由三部分构成: (1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分...
请考虑一个最坏情况O(nlogn)的算法确定n个元素的逆序对数目。 注意此题请勿用O(n^2)的简单枚举去实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中...
求解逆序对数是算法设计的经典题目,也是难以理解的分治算法,本算法采用分治思想利用递归将程序效率提高到nlogn值得学习算法的人参考
逆序对(归并排序)O(nlogn).cpp
逆序对,时间复杂度nlogn,采用修改后的合并排序算法
- 快速排序:采用分治策略,选取一个“基准”元素,然后将数组分为两部分,一部分所有元素小于基准,另一部分所有元素大于基准,然后递归对这两部分进行排序,平均时间复杂度为O(nlogn)。 - 归并排序:同样采用分治...
而求逆序对问题的算法同样基于分治,时间复杂度为O(nlogn)。 4. **代码实现**: 实现元素选择问题的C++代码采用了模板函数,定义了一个大小为size的数组,通过迭代和交换操作,将数组按中枢元素划分,最终找到第k...
逆序对是指在一个序列中,如果一个元素的值大于它后面元素的值,那么它们就构成一个逆序对。为了找到整个序列中的逆序对数量,我们可以使用归并排序的分治思想。归并排序在合并两个有序子数组时,可以统计出在合并...
分治法也被用于计算逆序对的数量,如题目所示,通过类似归并排序的过程,将数组分为两半,递归地计算逆序对,再进行合并,其时间复杂度为O(nlogn)。 4. **逆序对**: 在一个排序序列中,如果两个元素的位置相反,...
通过递归计算,可以得到整个序列的逆序对总数,同样保持了O(nlogn)的时间复杂性。 在以上两个例子中,分治算法的优势在于它可以将复杂的问题简化为更小的、易于处理的部分,同时保证了解决方案的高效性。通过对子...
求逆序对数: 给一列数a1,a2......an,求它的 逆序对数,即有多少个有序对 (i,j),使得i < j 但 ai > aj 第k小数: 输入n个整数和一个正整数k(1 <= k <= n), 输出这些整数从小到大排序后的第k个 11月13日 & ...
冒泡排序的基本思想是:依次比较相邻的元素,如果逆序则交换直到整个序列有序。冒泡排序的优点是简单易懂,实现起来很容易,但缺点是时间复杂度高,效率不高。 快速排序 快速排序是一种高效的排序算法,时间复杂度...
- 冒泡排序:不断交换相邻的逆序元素,直到序列变为有序。它的时间复杂度为O(n^2),适合小规模或基本有序的数据。 - 快速排序:通过“分区”操作将数组分为两部分,然后对这两部分递归地进行排序。平均时间复杂度...
**冒泡排序**是最基础的排序算法之一,通过不断交换相邻的逆序元素来逐步排序。每一轮遍历都能确保最大(或最小)的元素浮到数组的一端。冒泡排序的时间复杂度为O(n^2),适用于小规模或近乎有序的数组。 **快速排序...
10. **1010 I love permutation**:这题涉及排列的逆序对计算。通过对排列进行排序,可以计算逆序对的奇偶性,从而解决问题。 11. **1011 I love max and multiply**:要求找到满足特定条件的最大乘积。可以使用...
平均时间复杂度为O(nlogn),但在最坏情况下(已排序或逆序)为O(n^2)。 5. 归并排序:也是基于分治,将序列分为两半分别排序,然后合并两个已排序的子序列。无论输入顺序如何,其时间复杂度总是O(nlogn),但需要...