AcWing 788. 逆序对的数量_Java

简介: AcWing 788. 逆序对的数量_Java

活动 - AcWing

用暴力会超时,所以选择归并排序



 static int N=1000010;
    public static void main(String[] args)  {
        int []arr=new int[N];
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for (int i = 0; i < n; i++) {
            arr[i]=sc.nextInt();
        }
        System.out.println(merge_sort(arr, 0, n - 1));
    }
    private static long merge_sort(int[] arr, int l, int r) {
        if(l>=r) return 0;
        int mid=l+r>>1;
        long result=0;
         int []s=new int[r-l+1];
        result=merge_sort(arr,l,mid)+merge_sort(arr,mid+1,r);
        int i=l,j=mid+1,k=0;
        while (i<=mid &&j<=r){
            if(arr[i]<=arr[j]) s[k++]=arr[i++];
            else{
                s[k++]=arr[j++];
                result+=mid-i+1;
            }
        }
        while (i<=mid) s[k++]=arr[i++];
        while (j<=r) s[k++]=arr[j++];
        for (i = l, k = 0; i <= r; i++, k++) {
            arr[i] = s[k];
        }
        return result;
    }
目录
打赏
0
0
0
0
1
分享
相关文章
算法_逆序对_归并(java)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
剑指 Offer 51:数组中的逆序对 (Java分治思想)
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
123 0
逆序对(逆序对问题) 分而治之方法(分治法)java代码实现完整版(递归实现)
逆序对(逆序对问题) 分而治之方法(分治法)java代码实现完整版(递归实现)
434 0
逆序对(逆序对问题) 分而治之方法(分治法)java代码实现完整版(递归实现)
Java社招面试题:一个线程运行时发生异常会怎样?
大家好,我是小米。今天分享一个经典的 Java 面试题:线程运行时发生异常,程序会怎样处理?此问题考察 Java 线程和异常处理机制的理解。线程发生异常,默认会导致线程终止,但可以通过 try-catch 捕获并处理,避免影响其他线程。未捕获的异常可通过 Thread.UncaughtExceptionHandler 处理。线程池中的异常会被自动处理,不影响任务执行。希望这篇文章能帮助你深入理解 Java 线程异常处理机制,为面试做好准备。如果你觉得有帮助,欢迎收藏、转发!
65 14
Java 面试必问!线程构造方法和静态块的执行线程到底是谁?
大家好,我是小米。今天聊聊Java多线程面试题:线程类的构造方法和静态块是由哪个线程调用的?构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节有助于掌握Java多线程机制。下期再见! 简介: 本文通过一个常见的Java多线程面试题,详细讲解了线程类的构造方法和静态块是由哪个线程调用的。构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节对掌握Java多线程编程至关重要。
46 13
【JAVA】封装多线程原理
Java 中的多线程封装旨在简化使用、提高安全性和增强可维护性。通过抽象和隐藏底层细节,提供简洁接口。常见封装方式包括基于 Runnable 和 Callable 接口的任务封装,以及线程池的封装。Runnable 适用于无返回值任务,Callable 支持有返回值任务。线程池(如 ExecutorService)则用于管理和复用线程,减少性能开销。示例代码展示了如何实现这些封装,使多线程编程更加高效和安全。
|
1月前
|
java异步判断线程池所有任务是否执行完
通过上述步骤,您可以在Java中实现异步判断线程池所有任务是否执行完毕。这种方法使用了 `CompletionService`来监控任务的完成情况,并通过一个独立线程异步检查所有任务的执行状态。这种设计不仅简洁高效,还能确保在大量任务处理时程序的稳定性和可维护性。希望本文能为您的开发工作提供实用的指导和帮助。
113 17
|
2月前
|
Java—多线程实现生产消费者
本文介绍了多线程实现生产消费者模式的三个版本。Version1包含四个类:`Producer`(生产者)、`Consumer`(消费者)、`Resource`(公共资源)和`TestMain`(测试类)。通过`synchronized`和`wait/notify`机制控制线程同步,但存在多个生产者或消费者时可能出现多次生产和消费的问题。 Version2将`if`改为`while`,解决了多次生产和消费的问题,但仍可能因`notify()`随机唤醒线程而导致死锁。因此,引入了`notifyAll()`来唤醒所有等待线程,但这会带来性能问题。
Java—多线程实现生产消费者
Java 多线程 面试题
Java 多线程 相关基础面试题

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等