当前位置：首页 > article >正文

51. 数组中的逆序对

article 2024/9/19 22:47:45

comments: true
difficulty: 困难
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9851.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%80%86%E5%BA%8F%E5%AF%B9/README.md

面试题 51. 数组中的逆序对

题目描述

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

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

解法

方法一：归并排序

归并排序的过程中，如果左边的数大于右边的数，则右边的数与左边的数之后的数都构成逆序对。

时间复杂度 $\times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组长度。

Python3

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
    	def merge_sort(l, r):
	            if l >= r:
	                return 0
	            mid = (l + r) >> 1
	            ans = merge_sort(l, mid) + merge_sort(mid + 1, r) #对左右子序列进行递归排序，
	            
	            #以下为merge操作：先两个两个排序归并，再四个四个排序归并，，，
	            tmp = [] # 合并后的结果序列
	            i, j = l, mid + 1 # 左，右子序列的指针
	            while i <= mid and j <= r:
	                if nums[i] <= nums[j]: #1.如果左子序列的元素小于等于右子序列的元素，将左子序列的元素添加到结果序列中
	                    tmp.append(nums[i])
	                    i += 1 #2.左子序列指针向后移动一位
	                else:
	                    ans += mid - i + 1 #核心：如果左边的数大于右边的数，则右边的数与 左边的数之后的数 都构成逆序对
	                    tmp.append(nums[j]) #3.否则，将右子序列的元素添加到结果序列中
	                    j += 1 #4.右子序列指针向后移动一位
	            # 将剩余的元素直接添加到结果序列中     
	            tmp.extend(nums[i : mid + 1])
	            tmp.extend(nums[j : r + 1])
	            nums[l : r + 1] = tmp
	            return ans
	        return merge_sort(0, len(nums) - 1)

Java

class Solution {
    private int[] nums;
    private int[] t;

    public int reversePairs(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        this.t = new int[n];
        return mergeSort(0, n - 1);
    }

    private int mergeSort(int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = (l + r) >> 1;
        int ans = mergeSort(l, mid) + mergeSort(mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                t[k++] = nums[i++];
            } else {
                ans += mid - i + 1;
                t[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            t[k++] = nums[i++];
        }
        while (j <= r) {
            t[k++] = nums[j++];
        }
        for (i = l; i <= r; ++i) {
            nums[i] = t[i - l];
        }
        return ans;
    }
}

C++

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int t[n];
        function<int(int, int)> mergeSort = [&](int l, int r) -> int {
            if (l >= r) {
                return 0;
            }
            int mid = (l + r) >> 1;
            int ans = mergeSort(l, mid) + mergeSort(mid + 1, r);
            int i = l, j = mid + 1, k = 0;
            while (i <= mid && j <= r) {
                if (nums[i] <= nums[j]) {
                    t[k++] = nums[i++];
                } else {
                    ans += mid - i + 1;
                    t[k++] = nums[j++];
                }
            }
            while (i <= mid) {
                t[k++] = nums[i++];
            }
            while (j <= r) {
                t[k++] = nums[j++];
            }
            for (i = l; i <= r; ++i) {
                nums[i] = t[i - l];
            }
            return ans;
        };
        return mergeSort(0, n - 1);
    }
};

Go

func reversePairs(nums []int) int {
	n := len(nums)
	t := make([]int, n)
	var mergeSort func(l, r int) int
	mergeSort = func(l, r int) int {
		if l >= r {
			return 0
		}
		mid := (l + r) >> 1
		ans := mergeSort(l, mid) + mergeSort(mid+1, r)
		i, j, k := l, mid+1, 0
		for i <= mid && j <= r {
			if nums[i] <= nums[j] {
				t[k] = nums[i]
				k, i = k+1, i+1
			} else {
				ans += mid - i + 1
				t[k] = nums[j]
				k, j = k+1, j+1
			}
		}
		for ; i <= mid; i, k = i+1, k+1 {
			t[k] = nums[i]
		}
		for ; j <= r; j, k = j+1, k+1 {
			t[k] = nums[j]
		}
		for i = l; i <= r; i++ {
			nums[i] = t[i-l]
		}
		return ans
	}
	return mergeSort(0, n-1)
}

TypeScript

function reversePairs(nums: number[]): number {
    const mergeSort = (l: number, r: number): number => {
        if (l >= r) {
            return 0;
        }
        const mid = (l + r) >> 1;
        let ans = mergeSort(l, mid) + mergeSort(mid + 1, r);
        let i = l;
        let j = mid + 1;
        const t: number[] = [];
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                t.push(nums[i++]);
            } else {
                ans += mid - i + 1;
                t.push(nums[j++]);
            }
        }
        while (i <= mid) {
            t.push(nums[i++]);
        }
        while (j <= r) {
            t.push(nums[j++]);
        }
        for (i = l; i <= r; ++i) {
            nums[i] = t[i - l];
        }
        return ans;
    };
    return mergeSort(0, nums.length - 1);
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
    const mergeSort = (l, r) => {
        if (l >= r) {
            return 0;
        }
        const mid = (l + r) >> 1;
        let ans = mergeSort(l, mid) + mergeSort(mid + 1, r);
        let i = l;
        let j = mid + 1;
        let t = [];
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                t.push(nums[i++]);
            } else {
                ans += mid - i + 1;
                t.push(nums[j++]);
            }
        }
        while (i <= mid) {
            t.push(nums[i++]);
        }
        while (j <= r) {
            t.push(nums[j++]);
        }
        for (i = l; i <= r; ++i) {
            nums[i] = t[i - l];
        }
        return ans;
    };
    return mergeSort(0, nums.length - 1);
};

C#

public class Solution {
    private int[] nums;
    private int[] t;

    public int ReversePairs(int[] nums) {
        this.nums = nums;
        int n = nums.Length;
        this.t = new int[n];
        return mergeSort(0, n - 1);
    }

    private int mergeSort(int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = (l + r) >> 1;
        int ans = mergeSort(l, mid) + mergeSort(mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                t[k++] = nums[i++];
            } else {
                ans += mid - i + 1;
                t[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            t[k++] = nums[i++];
        }
        while (j <= r) {
            t[k++] = nums[j++];
        }
        for (i = l; i <= r; ++i) {
            nums[i] = t[i - l];
        }
        return ans;
    }
}

Swift

class Solution {
    private var nums: [Int] = []
    private var temp: [Int] = []

    func reversePairs(_ nums: [Int]) -> Int {
        self.nums = nums
        let n = nums.count
        self.temp = [Int](repeating: 0, count: n)
        return mergeSort(0, n - 1)
    }

    private func mergeSort(_ left: Int, _ right: Int) -> Int {
        if left >= right {
            return 0
        }
        let mid = (left + right) / 2
        var count = mergeSort(left, mid) + mergeSort(mid + 1, right)
        var i = left
        var j = mid + 1
        var k = left

        while i <= mid && j <= right {
            if nums[i] <= nums[j] {
                temp[k] = nums[i]
                i += 1
            } else {
                count += mid - i + 1
                temp[k] = nums[j]
                j += 1
            }
            k += 1
        }

        while i <= mid {
            temp[k] = nums[i]
            i += 1
            k += 1
        }

        while j <= right {
            temp[k] = nums[j]
            j += 1
            k += 1
        }

        for i in left...right {
            nums[i] = temp[i]
        }

        return count
    }
}