首页 > 试题广场 >

数组中的逆序对

[编程题]数组中的逆序对

热度指数：846949 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P mod 1000000007

数据范围：对于 $50\%$ 的数据, $size\leq 10^4$
对于 $100\%$ 的数据, $size\leq 10^5$

数组中所有数字的值满足 $0 \le val \le 10^9$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

输入描述:

题目保证输入的数组中没有的相同的数字

示例1

输入

[1,2,3,4,5,6,7,0]

输出

示例2

输入

[1,2,3]

输出

算法知识视频讲解

Python 3

taxueguilai

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    mod = 1000000007
    def merge(self, left, right, data):
        # 只有一个参数或者越界的停止划分
        if left >= right:
            return 0
        mid = (left + right) // 2
        # 左右划分合并
        res = self.merge(left, mid, data) + self.merge(mid+1, right, data)
        # 防止溢出，即防止多轮叠加后res值太大，每轮直接取模
        res %= self.mod
        tmp = []
        i, j = left, mid+1
        for _ in range(left, right+1):
            # 左边的数先遍历完，剩下的全是右边的数
            if i == mid+1:
                tmp.append(data[j])
                j += 1
            # 要么是右边的数先遍历完，要么是左边的数比右边的数小
            elif j == right+1&nbs***bsp;data[i] < data[j]:
                tmp.append(data[i])
                i += 1
            # 左边的数比右边的数大，即为 逆序对，进行统计
            else:
                tmp.append(data[j])
                j += 1
                res += mid - i + 1  
        # 更新 data 数据
        data[left:right+1] = tmp
        return res % self.mod

    def InversePairs(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        return self.merge(0, n-1, nums)

编辑于 2023-07-01 11:19:02 回复(0)

Python 3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        length = len(data)
        nums = [0 for i in range(length)]
        # 记录逆序数
        sum = 0
        # 步长
        step = 1
        while step < length:
            start = 0
            i = 0
            while start < length:
                mid = start + step
                l, r = 0, 0
                while mid + r < length and l < step and r < step:
                    if data[start + l] > data[mid + r]:
                        nums[i] = data[mid + r]
                        r = r + 1
                        sum = sum + mid - start - l
                    else:
                        nums[i] = data[start + l]
                        l = l + 1
                    i = i + 1
                while start + l < length and l < step:
                    nums[i] = data[start + l]
                    l = l + 1
                    i = i + 1
                while mid + r < length and r < step:
                    nums[i] = data[mid + r]
                    r = r + 1
                    i = i + 1
                start = start + step * 2
            for c in range(length):
                data[c] = nums[c]
            print(data)
            nums = [0 for i in range(length)]
            step = step * 2
        mod = sum % 1000000007
        return mod

发表于 2022-09-12 16:16:02 回复(0)

Python 3

Keosu

二分查找插入

import bisect
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        count = 0
        sorted_data = []
        for i in data:
            count += len(sorted_data) - bisect.bisect_right(sorted_data, i)  
            bisect.insort_right(sorted_data, i) 
        return count % 1000000007

发表于 2022-08-01 08:42:39 回复(0)

Python 3

小小金木

class Solution:
def InversePairs(self , data: List[int]) -> int:
# write code here
a = 0
while len(data) > 1:
m = min(data)
a += data.index(m)
data.remove(m)

return a

我这个超时应该怎么解决啊

发表于 2022-07-31 21:24:54 回复(0)

Python 3

风软一江山

#并归排序方法
class Solution:
    def mergeSort(self, blist, start, end):
        if start >= end:
            return 0
        mid = (start + end) // 2
        count1 = self.mergeSort(blist, start, mid)
        count2 = self.mergeSort(blist, mid + 1, end)
        count = self.merge(blist, start, mid, end)
        return count + count1 + count2

    def merge(self, alist, left, center, right):
        length = right - left + 1
        temp = [0] * length
        tempIndex = 0
        _left = left
        _right = center + 1
        count = 0
        while _left <= center and _right <= right:
            if alist[_left] > alist[_right]:
                temp[tempIndex] = alist[_right]
                tempIndex += 1
                _right += 1
                count += center - _left + 1 # 合并排序的时候如果左边大于右边第一位，那么左边所有元素都大于右边第一位，可以组成逆序对
            else:
                temp[tempIndex] = alist[_left]
                tempIndex += 1
                _left += 1
        while _right <= right:
            temp[tempIndex] = alist[_right]
            tempIndex += 1
            _right += 1
        while _left <= center:
            temp[tempIndex] = alist[_left]
            tempIndex += 1
            _left += 1
        alist[left:left+length] = temp[0:length]
        return count

    def InversePairs(self, arr: List[int]) -> List[int]:
        return self.mergeSort(arr, 0, len(arr) - 1) % 1000000007

发表于 2022-07-27 00:02:37 回复(1)

Python 3

一万个小仙女

运行超时🤣

s = list(map(int,(input()[1:-1]).split(',')))

a = 0
for i in range(len(s)-1):
for j in range(i+1,len(s)):
if s[i] > s[j]:
a += 1
b = a % 1000000007
print(b)

发表于 2022-06-17 21:13:52 回复(0)

Python 3

牛客745881206号

class Solution:
def InversePairs(self , data: List[int]) -> int:
# write code here
P=0
data1=[]
i=0
k=1000000007
if len(data)<=1:
return 0
while i<(len(data)-1):
if data[i]>data[i+1]:
P+=1
i+=1

return P%k

哪里错了？

发表于 2022-06-05 16:24:13 回复(0)

Python 3

Vivimore

归并排序思想
时间复杂度：O(nlogn) 空间复杂度：O(n)

class Solution:
    sum_ = 0
    def merge_sort(self, data):
        n = len(data)
        if n <= 1:
            return data
        mid = n // 2
        left = self.merge_sort(data[:mid])
        right = self.merge_sort(data[mid:])
        l, r = 0, 0
        temp = []
        while l < len(left) and r < len(right):
            if left[l] > right[r]:
                self.sum_ += len(left) - l
                temp.append(right[r])
                r += 1
            else:
                temp.append(left[l])
                l += 1
        temp += left[l:]
        temp += right[r:]
        return temp
    def InversePairs(self , data: List[int]) -> int:
        self.merge_sort(data)
        return self.sum_ % 1000000007

发表于 2022-05-16 12:48:11 回复(0)

Python 3

刘轶

import bisect
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        li = []
        ans = 0
        
        for i in range(len(data)):
            index = bisect.bisect_left(li, data[i])
            ans += len(li) - index
#             li.insert(index, data[i])
            li[index:index] = [data[i]]
        
        return ans %  1000000007

发表于 2022-04-16 13:04:25 回复(0)

Python 3

想搞机器学习的小白


class Solution:
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        self.count = 0
        def Merge_sort(arr):
            if len(arr)==1:return arr
            left = Merge_sort(arr[:len(arr)//2])
            right = Merge_sort(arr[len(arr)//2:])
            i,j =0,0
            tmp = []
            while i <len(left) and j <len(right):
                if left[i]<right[j]:
                    tmp.append(left[i])
                    i+=1
                else:
                    tmp.append(right[j])
                    self.count+=len(left)-i
                    j+=1
            return tmp+left[i:]+right[j:]
        Merge_sort(data)
        return self.count%1000000007

发表于 2022-04-09 16:55:03 回复(0)

Python 3

miao111

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param data int整型一维数组
# @return int整型
# #
class Solution:
def InversePairs(self , data: List[int]) -> int:
# # write code here

def merge_sort(l, r):
# 终止条件
if l >= r: return 0
# 递归划分
m = (l + r) // 2
res = merge_sort(l, m) + merge_sort(m + 1, r)
# 合并阶段
i, j = l, m + 1
tmp[l:r + 1] = data[l:r + 1]
for k in range(l, r + 1):
if i == m + 1:
data[k] = tmp[j]
j += 1
elif j == r + 1 or tmp[i] <= tmp[j]:
data[k] = tmp[i]
i += 1
else:
data[k] = tmp[j]
j += 1
res += m - i + 1 # 统计逆序对
return res
tmp = [0] * len(data)

return merge_sort(0, len(data) - 1) % 1000000007

可参考链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/

发表于 2022-03-17 21:46:59 回复(0)

Python 3

kinter1

class Solution:
    def InversePairs(self , data: List[int]) -> int:
        self.count = 0
        def merge(data1, data2):
            data = []
            while data1 and data2:
                if data1[0] <= data2[0]:
                    data.append(data1.pop(0))
                else:
                    data.append(data2.pop(0))
                    self.count += len(data1)
            data.extend(data1 if data1 else data2)
            return data
        def merge_sort(data):
            if len(data) == 1:
                return data
            K = len(data) // 2
            data1 = merge_sort(data[:K])
            data2 = merge_sort(data[K:])
            return merge(data1, data2)
        merge_sort(data)
        return self.count % 1000000007

发表于 2022-03-06 21:23:05 回复(0)

Python 3

MiaoZzz

class Solution:
    count = 0
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        def mergeSort(arr, left, right):
            if left >= right:
                return []
            mid = (left + right) // 2
            mergeSort(arr, left, mid)
            mergeSort(arr, mid + 1, right)
            merge(arr, left, mid, right)
        
        def merge(arr, left, mid, right):
            tmp = []
            i, j = left, mid + 1
            while i <= mid and j <= right: 
                if arr[i] <= arr[j]:
                    tmp.append(arr[i])
                    i += 1
                else:
                    tmp.append(arr[j])
                    j += 1
                    self.count = self.count%1000000007 + (mid - i +1)
            while(i <= mid):
                tmp.append(arr[i])
                i +=1
            while(j <= right):
                tmp.append(arr[j])
                j +=1
            for index in range(len(tmp)):
                arr[left + index] = tmp[index]
        if len(data) > 0:
            mergeSort(data, 0, len(data) -1)
        return self.count

发表于 2022-03-03 20:52:14 回复(0)

Python 3

JSFaner

class Solution:
    def InversePairs(self , data: List[int]) -> int:
        if len(data) < 2: return 0
        big,small = [],[]
        res,pre = 0,data[0]
        for num in data[1:]:
            if num > pre: 
                big.append(num)
            else:
                small.append(num)
                res = res + len(big) + 1
        return (res + self.InversePairs(big) + self.InversePairs(small))%1000000007

发表于 2022-02-18 09:28:13 回复(0)

Python 3

up_zhang

import bisect

class Solution:
    def InversePairs(self , data: List[int]) -> int:
        num_list= []  #  定义已经遍历过的元素的有序数组
        ans = 0
        for i in range(len(data)):
            num = data[i]
            # 当前元素 在有序数组中的排序位置
            index = bisect.bisect_right(num_list, num)
            # 随着遍历，维护一个有序数组，
            num_list.insert(index, num)
            # 根据在有序数组中的排序位置 计算有多少个大于这个数的值
            a = len(num_list) -index -1
            ans += a
        return ans % 1000000007

发表于 2022-01-19 00:09:07 回复(0)

Python 3

牛客470684666号

import bisect
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        if not data:
            return 0
        if len(data)==1:
            return 0
        sort_data = [data[0]]
        count = 0
        for c in data[1:]:
            index = bisect.bisect(sort_data, c)
            if index==len(sort_data):
                sort_data.append(c)
            else:                
                count = count+len(sort_data)-index
                sort_data.insert(index, c)
        return count%1000000007

看到都在说归并排序，其实也可以用二分查找。

主要思想是建立一个有序的数组，对于data中的每个数，分别查找在有序数组中的插入位置，然后***去，如果插入位置是在最后，那就没有逆序，如果是在前面，就构成了有序数组长度-插入位置序号个逆序对。

python自带的二分查找bisect复杂度是logn，所以总复杂度为nlogn，当然也可以自己实现二分查找

发表于 2022-01-18 23:42:59 回复(0)

Python 3

bytedancers

class Solution:
    def InversePairs(self, data):
        # write code here
        res = 0
        aux = [0] * len(data)
        MOD = 10 ** 9 + 7
        def mergesort(i, j):
            if i >= j:
                return 
            nonlocal res
            mid = (i + j) // 2
            mergesort(i, mid)
            mergesort(mid+1, j)
            aux[i:j+1] = data[i:j+1]
        
            m, n = mid, j
            cur = j
            while m >=i&nbs***bsp;n >= mid+1:
                if n < mid + 1&nbs***bsp;(m >= i and aux[m] > aux[n]):
                    res += n - mid
                    data[cur] = aux[m]
                    cur -= 1
                    m -= 1
                else:
                    data[cur] = aux[n]
                    cur -= 1
                    n -= 1
        mergesort(0, len(data) - 1) 
        return res % MOD

发表于 2021-09-04 16:24:29 回复(0)

Python 3

大霞上仙

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.array = []
self.ret = 0

def merge(self, data, l, temp, r, array):
i = l
j = temp+1
array.clear()
while i<=temp and j<=r:
if data[i]<=data[j]:
array.append(data[i])
i += 1
else:
array.append(data[j])
j += 1
self.ret = self.ret + temp - i + 1
self.ret = self.ret%1000000007

while i <= temp:
array.append(data[i])
i += 1

while j <= r:
array.append(data[j])
j += 1
data[l:r+1] = array

def paixu(self, data, l ,r, array):
if l >= r:
return
temp = l + (r- l)//2
self.paixu(data, l, temp, array)
self.paixu(data, temp+1, r, array)
self.merge(data, l, temp, r, array)

def InversePairs(self, data):
# write code here
self.paixu(data,0, len(data)-1, self.array)
return self.ret

发表于 2021-08-21 16:57:03 回复(0)