数组中的逆序对—Python非归并解法

曾经终败给现在 2022-05-14 02:56 146阅读 0赞

**题目：**在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

该问题的最好解法是类似归并排序的解法，时间复杂度为O(nlogn)，网上相关介绍博客也很多，这里给出一个**非归并解法**，复杂度会高一点，但想法非常巧妙，代码非常简易。

以一个例子来说明：

输入数组：data=\[3,2,1,5,4,6,0,7\]

排序好数组：dataSorted=\[0,1,2,3,4,5,6,7\]

顺序遍历dataSorted数组，第一个元素0是最小的元素，因此在data数组中，0前面有多少个数，就有多少个逆序对。在0检测完之后，将0从data数组中删除，data=\[3,2,1,5,4,6,7\]，dataSorted数组遍历到1，而1其实就是\[1,2,3,4,5,6,7\]中的最小元素

因此，原问题就变为子问题：

输入数组：data=\[3,2,1,5,4,6,7\]

排序好数组：dataSorted=\[1,2,3,4,5,6,7\]

……

重复上述步骤直到遍历到最后一个元素。

函数代码如下：

def InversePairs(data):
        count = 0
        copy = [i for i in data]
        copy.sort()
    
        for i in range(len(copy)):
            count += data.index(copy[i])
            data.remove(copy[i])
    
        return count

注意第三行不能直接copy = data，因为这样是浅复制，他只是将原有的data数组打上一个新标签，所以当其中一个标签被改变的时候，数组就会发生变化，另一个标签也会随之改变。

而用copy = \[i for i in data\]相当于深复制，即将原数组重新复制一份给copy，两者就不会相互影响了，但需要多一份数组的内存空间，而浅复制不会重新占用空间。

**复杂度分析：**

sort排序复杂度为O(nlogn)；单次index查找复杂度为O(lgn)，要查找n次，复杂度也为O(nlogn)；单次remove操作中：查找该数的复杂度为O(lgn)，移动该数后面的数复杂度为O(n)，因此复杂度为O(n)，要remove操作n次，复杂度为O(n^2)；因此总的复杂度为O(n^2)。

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关数组中的逆序对

一、题目在数组中，如果前一个数字大于后一个数字，则两个数字组成一个逆序对。输入一个数组，求逆序对总数。二、分析（1）暴力求解：顺序扫描这个数组，每扫描到一个数字，如

超、凢脫俗/ 2023年11月20日 07:37/ 0 赞/ 247 阅读

相关数组中的逆序对（归并排序思想）

利用归并排序思想这题没有看懂，转来暂存 ![aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vZmlsZXMvMjAxODA1M

心已赠人/ 2023年01月02日 06:23/ 0 赞/ 194 阅读

相关数组中的逆序对

![这里写图片描述][70] public class Solution { public int count=0; //方法一、暴力

系统管理员/ 2022年05月25日 10:38/ 0 赞/ 191 阅读

相关数组中的逆序对

写在前面 > 题目：剑指offer-数组中的逆序对 > 考点：归并排序。知识点归并排序要求 > 在数组中的两个数字，如果前面一个数字大于

约定不等于承诺〃/ 2022年05月18日 07:15/ 0 赞/ 168 阅读

相关数组中的逆序对—Python非归并解法

题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。该问题的最好解法是类似归并排序的解法，时间

曾经终败给现在/ 2022年05月14日 02:56/ 0 赞/ 147 阅读

相关数组中的逆序对

[数组中的逆序对][Link 1] 题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的

Myth丶恋晨/ 2022年03月25日 15:38/ 0 赞/ 198 阅读

相关数组中的逆序对

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=19][

àì夳堔傛蜴生んèń/ 2022年03月20日 03:27/ 0 赞/ 224 阅读

相关【剑指Offer】（数组）数组中的逆序对（归并排序）

题目链接：[https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11

桃扇骨/ 2022年03月15日 05:06/ 0 赞/ 174 阅读

相关数组中的逆序对

时间限制：2秒空间限制：32768K 热度指数：259937 本题知识点：数组算法知识视频讲解题目描述在数组中的两个数字，如果前面一个数字大于后面的数

比眉伴天荒/ 2022年03月09日 10:50/ 0 赞/ 220 阅读

相关【牛客】求数组中的逆序对-归并思想

有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。给定一个int数组A和它的大小n，

本是古典何须时尚/ 2021年10月03日 01:58/ 0 赞/ 244 阅读