算法之逆序对

算法之逆序对

逆序对问题

​ 假设A[1..n]是一个有n个不同数的数组。若iA[j],则对偶(i, j)称为A的一个逆序对(inversion)。

  1. 列出数组{2, 3, 8, 6, 1}的5个逆序对
  2. 由集合{1, 2, ..., n}中的元素构成的什么数组具有最多的逆序对?它有多少逆序对?
  3. 插入排序的运行时间与输入数组中的逆序对的数量有什么关系?
  4. 给出一个求在n个元素的任何排列中逆序对数量的算法,最坏时间复杂度为: \(\Theta\)(nlgn)
  5. 根据定义易得,逆序对为:(2, 1)、(3, 1)、(8, 6)、(8, 1)、(6, 1)
  6. 当数组元素恰好为n个元素从大到小排列时,拥有最多的逆序对。此时逆序对为: (n - 1) + (n -2) + (n - 3) + ... + 1 = n(n - 1) / 2
  7. 根据插入排序的实现过程,不难得出每次从未排序数组选择一个值arr[j]插入已排序数组的时候,所需要的移动次数,即为以arr[j]为右侧值的逆序对的个数。这个特性也可以设计出一个时间复杂度为: \(\Theta\)(\(n^2\))的算法。当然这种指数级别复杂度的算法我们直接PASS
  8. 不难想到\(\Theta\)(nlgn)算法复杂度的归并排序。其实归并排序在分治的时候不会改变逆序对的个数。只有在合并的时候,才会因为逆序对的出现导致右侧提前被合入原数组。其实修改点主要在两个方面:
  • 声明一个全局变量用来存储总的次数
  • 在右侧提前被合入原数组的时候对总次数进行累加(只需要改归并排序的merge方法, 归并排序请参照http://www.cnblogs.com/Kidezyq/p/8379267.html

具体源代码如下:

private static int count;

private static void merge(int[] arr, int startIndex, int midIndex, int endIndex) {
    /**
     * 合并策略: 
     * 1. 新建两个数组,分别存取左半部分排好序的数组和右半部分排好序的数组
     * 2. 分别从左右两个数组最开始下标开始遍历,选取较小的依次放入原数组对应位置
     * 3. 最终如果左右数组中有一个已经遍历完成,另一个数组所剩的元素直接放入元素组后面部分即可
     */
    // STEP1
    int[] leftArr = new int[midIndex - startIndex];
    int[] rightArr = new int[endIndex - midIndex];
    System.arraycopy(arr, startIndex, leftArr, 0, leftArr.length);
    System.arraycopy(arr, midIndex, rightArr, 0, rightArr.length);
    
    // STEP2
    int k = startIndex; // 存储原数组中的下标
    int i = 0;          // 存储左边数组的下标
    int j = 0;          // 存储右边数组的下标
    while (i < leftArr.length && j < rightArr.length) {
        // 将较小的元素复制到元素组对应下标k,并且移动较小元素所在数组下标
        if (leftArr[i] < rightArr[j]) {
            arr[k++] = leftArr[i++];    
        } else {
            // 此时说明 arr[i]到arr[leftArr.length - 1]的值都比arr[j]大,即此时以arr[j]结尾的逆序对个数为: 
            count += leftArr.length - i;
            arr[k++] = rightArr[j++];
        }
    }
    
    // STEP3
    if (i < leftArr.length) {
        System.arraycopy(leftArr, i, arr, k, leftArr.length - i);
    } else if (j <= rightArr.length) {
        System.arraycopy(rightArr, j, arr, k, rightArr.length - j);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q171 Excel Sheet Column Number

Related to question Excel Sheet Column Title Given a column title as appear in a...

3195
来自专栏恰同学骚年

剑指Offer面试题:31.两个链表的第一个公共节点

  碰到这道题,很多人的第一反应就是蛮力法:在第一链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和...

461
来自专栏计算机视觉与深度学习基础

leetcode 6 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of...

1817
来自专栏海纳周报

详解Python的is操作符

is 操作符是Python语言的一个内建的操作符。它的作用在于比较两个变量是否指向了同一个对象。 与 == 的区别 class A(): def __i...

4149
来自专栏salesforce零基础学习

salesforce 零基础学习(二十六)自定义图表chart简单介绍(使用apex和VF实现)

chart在报表中经常使用到,他可以使报表结果更加直观的展现给用户。salesforce支持VF和apex代码来更好的展示chart。 chart分类:常用的图...

1728
来自专栏趣谈编程

外部排序

当我们要排序的文件太大以至于内存无法一次性装下的时候,这时候我们可以使用外部排序,将数据在外部存储器和内存之间来回交换,以达到排序的目的

960
来自专栏苦逼的码农

从0打卡leetcode之day7--Z字形变换

好久没打卡了,虽然自己有看题,不过最近在忙其他事,没什么时间写出来。马上就要开学了,开学了可能反而会更有时间来刷题吧。可以在上课的时间段来写,,哈哈。毕竟很少听...

581
来自专栏阮一峰的网络日志

React 测试入门教程

越来越多的人,使用React开发Web应用。它的测试就成了一个大问题。 React的组件结构和JSX语法,不适用传统的测试工具,必须有新的测试方法和工具。 本文...

3284
来自专栏everhad

android输入限制

前言2 使用EditText让用户输入文字时,需要对输入验证。除过验证是否有效的逻辑不同,EditText的基本交互是一样的: 考虑到可能的copy,past...

1786
来自专栏yl 成长笔记

二叉搜索树 (BST) 的创建以及遍历

二叉搜索树(Binary Search Tree) : 属于二叉树,其中每个节点都含有一个可以比较的键(如需要可以在键上关联值), 且每个节点的键都大于其左子树...

683

扫描关注云+社区