`

逆序对问题 (O(nlgn))

 
阅读更多

 

    问题描述

      在数组arr[]中,i < j  , 如果 arr[i] > arr[j] 那么就存在一个逆序对

      目的就是求出逆序对的数目。

 

   算法

      暴力求解,O(n^2);

      下面运用了一种很巧妙的方法,通过归并排序的归并过程,进行逆序对的统计!

       具体例子分析:

       比如 1 5 3 2 4

       当 1 3 5 与 2 4 合并的时候,

       a. 1 < 2 , 所以1放入

       b.  3>2 , 同理可得到3后面的元素也一定>2 ,所以逆序对 += 左边的长度 - 3的下标

        同理 , 5 > 4 , ...

        在归并的过程,完成了逆序对的统计,之所以可以这样,归并排序过程中,左边的子集一定在右边子集的前面,所以不用考虑先后

        关系了,而且,元素都是排好序了的!

 

    实现代码

public class ReversePair {

	public static void main(String[] args) {
		ReversePair rp = new ReversePair();
		int[] arr = {1,3,7,8,2,4,6,5};
		rp.divide(arr, 0, arr.length - 1);
System.out.println(rp.pairs);
	}
	
	private int pairs ;
	
//	归并算法的思想解决 逆序对
//	暴力方法求解的时候,就是对没对元素比较 , O(n^2)
	public void divide(int[] arr , int low , int high) {
		if(low < high) {
			int mid = (low + high) / 2;
			divide(arr , low , mid );
			divide(arr , mid + 1 , high);
			merge(arr , low , mid ,high);
		}
	}

	private void merge(int[] arr, int low, int mid, int high) {
		int[] left = new int[mid - low + 2];
		int[] right = new int[high - mid + 1];
		
		int t = 0;
		for (int i = low ; i <= mid ; i++) {
			left[t++] = arr[i];
		}
		t = 0;
		for (int i = mid + 1 ; i <= high ; i++) {
			right[t++] = arr[i];
		}
    //	设置哨兵,要不你怎么知道数组所有元素已经合并了?	
		left[left.length - 1] = Integer.MAX_VALUE;
		right[right.length - 1] = Integer.MAX_VALUE;
		
		int lLen = left.length;
		int lt = 0 , rt = 0;
//		 这里不要 i = 0了!!
		for(int i = low ; i <= high ; i++) {
			if(right[rt] >= left[lt]){
				arr[i] = left[lt];
				lt++;
			} else { // 如果右边的小于左边的话,那么必然小于左边元素后面的所有元素!
				arr[i] = right[rt];
				rt++;
//				注意这里要-1 , 因为你设一个哨兵!
				pairs += (lLen - lt - 1);
			}
		}
		
	}

}

 

分享到:
评论

相关推荐

    逆序对问题

    请考虑一个最坏情况O(nlogn)的算法确定n个元素的逆序对数目。 注意此题请勿用O(n^2)的简单枚举去实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中...

    Python程序计算逆序对数量,采用双循环结构遍历数组查找逆序对

    内容概要:本文详细介绍了用 Python 实现的一个简单逆序数计算程序,采用双循环结构遍历数组查找逆序对。文中还提及了若希望提高运算效率时可进一步选择低时间复杂度的解决方案。 适合人群:Python 初学者以及需要对...

    11087 统计逆序对

    请考虑一个最坏情况O nlogn 的算法确定n个元素的逆序对数目 注意此题请勿用O n^2 的简单枚举去实现 输入格式 第一行:n 表示接下来要输入n个元素 n不超过10000 第二行:n个元素序列 输出格式 逆序对的个数 ...

    算法-求逆序对(信息学奥赛一本通-T1311).rar

    对于求逆序对的问题,我们可以维护一个数组C,其中C[i]表示在数组A中,所有小于等于i的元素的个数。当数组A发生变化时,我们通过树状数组更新C[i]。 - 初始化C数组,C[i] = 0,然后遍历数组A,对每个元素A[i],在...

    算法-理论基础- 排序- 逆序对问题(包含源程序).rar

    逆序对问题在计算机科学和算法领域中是一个重要的概念,主要与排序算法和数据结构相关。逆序对,也称为倒序对,是指在一个已排序的序列中,如果一个元素大于其后面的一个或多个元素,那么这些元素对就被称为逆序对。...

    算法分析 统计逆序对

    请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。 一个n个元素序列的逆序对个数由三部分构成: (1)它的左半部分逆序对的个数,(2)加上右半部分逆序对的个数,(3)再加上左半部分...

    归并求逆序对 分治 递归

    逆序对问题在计算机科学与算法领域中是一个非常典型的应用场景,尤其适用于数据结构与算法的面试题目之中。 #### 逆序对定义 首先,我们需要明确什么是逆序对。在一个数组中,如果对于某两个索引 `i` 和 `j`(`i ...

    逆序对实现

    这些源代码可能展示了上述的一种或多种方法,通过阅读和分析代码,我们可以学习到如何在C语言中高效地处理逆序对问题,以及如何利用高级数据结构来优化算法。 总之,逆序对的计算是数据结构和算法领域的一个经典...

    逆序对(树状数组) C语言

    逆序对的数量可以反映出数组的有序程度,是许多算法问题的基础,如快速排序、归并排序等的分析。 树状数组,又称为线段树,是一种数据结构,主要用于处理区间查询和区间更新的问题。它的核心思想是将线性数组划分成...

    贪心法 逆序对问题

    贪心法求逆序对问题代码

    算法分析与设计-实验1-统计逆序对

    通过对逆序对统计实验的学习与实践,学生不仅加深了对归并排序算法的理解,还学会了如何利用算法解决实际问题。此外,通过编写和调试代码,学生的编程技能也得到了锻炼。该实验是理论与实践相结合的良好案例,有助于...

    归并求逆序对 C语言实现

    这种方法利用了分治的思想,通过递归将大问题分解为小问题,然后在合并阶段计算逆序对的数量。在 C 语言实现中,使用了辅助数组来存储排序结果,并通过指针操作完成合并过程。这种方法不仅能够有效地解决问题,而且...

    归与分治策略实例编程 统计给定数组中的逆序对个数

    统计给定数组中的逆序对个数。 给n个数a1,a2…an,如果存在存在ai&gt;aj,且i,则称这样的元素对,aj&gt;为一个逆序对 统计这n个数中逆序对的总数 比如说,n=5,a1到a5分别为5,3,1,4,3 则逆序对有 ,3&gt;,,1&gt;,,4&gt;,,3&gt;,,1&gt;,,3&gt;共6...

    POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】

    在编程竞赛中,题目"POJ1804 - Brainman"是一道要求高效解决逆序对问题的算法题。本题目的核心是利用归并排序(Mergesort)算法来实现逆序数的计算,以达到O(n log n)的时间复杂度,避免平方级别的效率消耗。 首先...

    逆序对.zip

    解决逆序对问题有多种方法,以下是一些常见的策略: 1. **直接遍历**:最直观的方法是两层循环遍历整个数组,但时间复杂度高达O(n^2),对于大规模数据并不适用。 2. **归并排序**:归并排序在合并过程中可以顺便...

    c++代码P1908逆序对

    c++代码P1908逆序对

    分治法求数组中的逆序数

    有一实数序列a1,a2,....an,若i且ai&gt;aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。

    C++源程序测试数组中有多少个逆序对

    测试输入的数组中有多少个逆序对,本程序在归并排序的基础上实现,时间复杂度为O(nlgn)

    统计数组中逆序对

    统计数组中的逆序对的个数,基于归并排序的思想,先拆分为单个元素,再合并为两个元素的数组,组内统计后,排序,进行组建统计

Global site tag (gtag.js) - Google Analytics