数据结构中的反转对问题

2025年3月17日 | 阅读 7 分钟

问题陈述

给定一个整数数组 nums，返回数组中逆序对的数量。

逆序对是一个满足以下条件的数对 (i, j)：

0 <= i < j < nums.length 且

nums[i] > 2 * nums[j]。

示例

输入: nums = [1,3,2,3,1]

输出 2

说明

输出表示给定数组中有两个逆序对。逆序对由两个元素 nums[i] 和 nums[j] 组成，其中 i < j 且 nums[i] > 2 * nums[j]。在提供的数组 [1,3,2,3,1] 中，数对 [3,1] 和 [3,1] 满足此条件，总共有两个逆序对。

示例 2

输入: nums = [2,4,3,5,1]

输出 3

说明

输出表示给定数组中有三个逆序对。当存在两个元素 nums[i] 和 nums[j]，索引 i < j 且 nums[i] > 2 * nums[j] 时，就会出现逆序对。在数组 [2,4,3,5,1] 中，数对 [4,1]、[5,1] 和 [3,1] 满足此条件，总共有三个逆序对。

使用双指针技术的Java方法

import java. util.Scanner; 
public class ReversePairs {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        // Input the length of the array
System.out.print("Enter the length of the array: ");
        int length = scanner.nextInt();
        int[] nums = new int[length]; 
        // Input the array elements
System.out.println("Enter the elements of the array:");
        for (int i = 0; i < length; i++) {
            nums[i] = scanner.nextInt();
        }
        // Create an instance of the Solution class
        Solution solution = new Solution();
        // Call the reversePairs method and print the result
        int result = solution.reversePairs(nums); 
System.out.println("Result: " + result); 
scanner.close();
    }
}
class Solution {
    // Method to merge two sorted subarrays
    public void merge(int[] arr, int start, int end, int mid) {
        int n1 = mid - start + 1;
        int n2 = end - mid;
        int[] res1 = new int[n1];
        int[] res2 = new int[n2]; 
        // Copy data to temporary arrays
        for (int i = 0; i < n1; i++) {
            res1[i] = arr[start + i];
        }
        for (int j = 0; j < n2; j++) {
            res2[j] = arr[mid + 1 + j];
        }
        // Merge the two arrays
        int i = 0, j = 0, k = start;
        while (i < n1 && j < n2) {
            if (res1[i] <= res2[j]) { 
arr[k++] = res1[i++];
            } else {
arr[k++] = res2[j++];
            }
        }
        // Copy remaining elements of res1[] and res2[]
     //This while loop works until the i is less than the value n1
  while (i < n1) {
            arr[k++] = res1[i++];
        }
         //This while loop works until the j is less than the value n2
        while (j < n2) {
            arr[k++] = res2[j++];
        }
    }
    // Method to count reverse pairs in a subarray
    public int check(int[] nums, int start, int end, int mid) {
        int right = mid + 1, count = 0;
        //the for loop will start from the start and it will run until the start value reaches the mid value.
        for (int i = start; i <= mid; i++) {
            while (right <= end && nums[i] > 2L * nums[right]) {   
right++;
            }
            count += right - mid - 1;
        }
        return count;
    }
    // Method to divide the array into halves and count reverse pairs
    public int divide(int[] nums, int start, int end) {
        int count = 0;
        if (start < end) {
            int mid = start + (end - start) / 2;
            count += divide(nums, start, mid);
            count += divide(nums, mid + 1, end);
            count += check(nums, start, end, mid); 
merge(nums, start, end, mid);
        }
        return count;
    }
    // Method to calculate the total number of reverse pairs in the array
    public int reversePairs(int[] nums) {
        return divide(nums, 0, nums.length - 1);
    }
}

输出

代码解释

该代码使用归并排序算法高效地计算给定数组中的逆序对数量。在归并过程中，它实现了双指针技术。
在 merge 方法中，通过使用两个指针（i 和 j）比较元素来合并两个已排序的子数组。如果第一个子数组中的元素大于第二个子数组中的元素，则表明存在逆序对。此类数对的数量会根据第一个子数组中剩余元素的数量递增。
在 check 方法中，第二个指针（right）遍历第二个子数组，以查找与第一个子数组中的元素形成逆序对的元素。
总而言之，双指针技术在归并排序算法合并已排序的子数组时，有效地识别并计数逆序对。

时间复杂度

由于归并排序算法，直到 divide 方法之后最终元素被递归地分成两半直到累积，时间复杂度为 O(n log n)。
check 方法将以线性时间 O(n) 运行，其中“n”代表数组大小。
整个过程的算法以归并排序为主导因素，其时间复杂度为 O(n log n)。

空间复杂度

空间复杂度为 O(n)，因为归并操作、递归调用和临时数组需要额外的空间，这与数组的大小成正比。

缺点

此外，上述解决方案的一个缺点是其大的空间复杂度。除了临时数组需要额外空间外，归并排序算法在所有阶段都执行归并操作。随着输入数组大小的相应增加，分配给临时数组的空间将以相同的定性方式增加，从而导致空间复杂度的增加。
在非常大的输入矩阵的情况下，这种额外的空间使用会变得相当显著，从而导致内存相关问题或影响在内存资源有限的设备上运行算法的效率。

使用归并排序的Java方法

import java. util.ArrayList;
import java. util.Scanner; 
public class ReversePairsCount {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        // Input for the length of the array
System.out.print("Enter the length of the array: ");
        int length = scanner.nextInt();
        int[] nums = new int[length];
        // Input for the values of each element in the array
System.out.println("Enter the values for each element in the array:");
        for (int i = 0; i < length; i++) {
            nums[i] = scanner.nextInt();
        }
        Solution solution = new Solution();
        int result = solution.reversePairs(nums); 
        // Output the result
System.out.println("Result: " + result); 
scanner.close();
    }
}
class Solution {
    int count; 
    // Method to find the reverse pairs count
    public int reversePairs(int[] nums) {
        count = 0;
        merger(nums, 0, nums.length - 1);
        return count;
    }
    // Method to merge two sorted arrays and count reverse pairs
    private ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right) {
ArrayList<Integer> ans = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < left.size() && j < right.size()) {
            if (left.get(i) > right.get(j)) {
ans.add(right.get(j));
                j++;
            } else {
ans.add(left.get(i));
                i++;
            }
        }
        if (i < left.size()) {
            while (i < left.size()) 
ans.add(left.get(i++));
        }
        if (j < right.size()) {
            while (j < right.size())   
ans.add(right.get(j++));
        }
        return ans;
    }
    // Method to count reverse pairs
    private void helper(ArrayList<Integer> left, ArrayList<Integer> right) {
        int i = 0;
        int j = 0;
        while (i < left.size() && j < right.size()) {
            if (left.get(i) > 2 * (long) right.get(j)) {
                count += left.size() - i;
                j++;
            } else {
                i++;
            }
        }
    }
    // Method to perform merge sort and count reverse pairs
    private ArrayList<Integer> merger(int[] nums, int start, int end) {
        if (start == end) {
ArrayList<Integer> temp = new ArrayList<>();   
temp.add(nums[start]);
            return temp;
        }
        int mid = (start + end) / 2; 
ArrayList<Integer> left = merger(nums, start, mid); 
ArrayList<Integer> right = merger(nums, mid + 1, end);
        helper(left, right);
        return merge(left, right);
    }
}

输出

代码解释

该代码实现了归并排序算法，以高效地计算数组中的逆序对数量。其工作原理如下：

归并排序： 数组被递归地分成两半，直到获得单个元素。这是“分”的步骤。
合并： 在合并过程中，将左半部分和右半部分的元素进行比较，并合并成一个排序后的数组。这是计算逆序对的地方。
计算逆序对： 在合并时，如果左半部分的元素大于右半部分元素的两倍，则表示存在逆序对。计数将根据左半部分中可能与右半部分当前元素形成逆序对的剩余元素数量递增。
基本情况： 当数组被简化为单个元素时，递归停止。

通过使用归并排序高效地对数组进行排序，并在合并阶段计算逆序对，该代码准确地确定了数组中存在的逆序对的总数。

时间复杂度

建议解决方案的时间复杂度为 O(n log n)，其中 n 是输入数组的长度。然而，缺点是归并排序过程基于将数组递归地分成两半，并且合并操作必须以线性时间执行，这与数组的大小成正比。

空间复杂度

空间复杂度为 O(n)，因为算法在合并过程中利用了一些额外的空间用于临时存储的数组。

下一主题使用多项式滚动哈希函数进行字符串哈希

数据结构中的反转对问题

问题陈述

使用双指针技术的Java方法

使用归并排序的Java方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的反转对问题

问题陈述

使用双指针技术的Java方法

使用归并排序的Java方法

相关帖子

二叉树的类型

冒泡排序和归并排序的区别

N 元树中给定节点的兄弟数量

在行和列排序的矩阵中搜索

中序遍历

二叉树的最低公共祖先

矩阵沿对角线镜像

搜索查询自动完成

提高密码强度

Cuckoo Hashing - 最坏情况 O(1) 查找

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器