数组中的逆序对

作者:神秘网友 发布时间:2021-02-10 19:50:08

数组中的逆序对

/*
      在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
    
输入: [7,5,6,4]
输出:  5 
*/
//其实就是归并排序  在左侧的一个元素大于右数组的一个元素时 左侧元素本身以及左数组剩余的元素都能组成一个逆序对
class Solution {
    private int count = 0;
    public int reversePairs(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(nums,0,nums.length-1,temp);
        return count;
    }

    public void mergeSort(int[] arr, int left, int right, int[] temp) {

        if (left  right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid+1, right, temp);
            merge(arr,left,mid,right,temp);
        }
        //return temp;
    }

    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int k = left;
        int j = mid + 1;
        int i = 0;
        while (k = mid  j = right) {
            if(arr[k]=arr[j]){
                temp[i++] = arr[k++];
            }else{
                count += mid-k+1;
                temp[i++] = arr[j++];
            }
        }
        while (k = mid){
            temp[i++] = arr[k++];
        }
        while (j = right){
            temp[i++] = arr[j++];
        }

        i = 0;
        while(left = right){
            arr[left++] = temp[i++];
        }
    }
}

数组中的逆序对 相关文章

  1. vuex中的 mapState,mapGetters,mapActions,mapMutations 的使用

    在vuex中有四大金刚分别是State, Mutations,Actions,Getters,本文对这四大金刚做了详细介绍,本文重点是给大家介绍vuex中的 mapState,mapGetters,mapActions,mapMutations 的使用,感兴趣的朋友一起看看吧 一、介绍 vuex里面的四大金刚:State, Mutatio

  2. 剑指 Offer 56 - II. 数组中数字出现的次数 II + 位运算

    剑指 Offer 56 - II. 数组中数字出现的次数 II Offer_56_2 题目详情 解题思路 java代码 package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/10 13:43 *//** * 题目描述:在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现

  3. Java中的基本运算符

    Java基本运算符 一、算术运算符 运算符:对常量或者变量进行操作的符号 表达式:用运算符把常量或者变量连接起来符合java语法的式子就可以称为表达式。 + 加法运算、字符串拼接运算 - 减法运算 * 乘法运算 / 除法运算 % 取模(mod)运算,两个数相除取余数 二

  4. Filter

    过滤器 1. 过滤中的所有代码,在过滤特定请求的时候都会执行 2. 必须要让过滤器继续执行 public class FilterEncoding implements Filter { @Override public void init(FilterConfig filterConfig) throws ServletException { System.out.println("已经初始

  5. c#中的数据类型转换

    //类型转换 推荐使用c#给我们的万能转换器Convert.数据类型(需要被转换的值); int num = 102; string strnum = num + ""; //等价于 num.ToString(); 需要转换的值.To数据类型(),+号起到连接字符串的作用,当两边都是数字起到相加的作用。 num = int.Parse(s

  6. 数组链表实现List

    数组链表 数组ArrayList Code: //可变数组class ArrayList_{ //初始容器大小 private static int DEFAULT_SIZE = 10; //容器 Object[] objects = new Object[DEFAULT_SIZE]; //当前的大小 private int size = 0; //添加元素 public void add(Object o){ //如

  7. 【题解】力扣992. K 个不同整数的子数组

    题目来源 992. K 个不同整数的子数组 题目描述:给定一个正整数数组 A ,如果 A 的某个子数组中不同整数的个数恰好为 K ,则称 A 的这个连续、不一定独立的子数组为 好子数组 。 思路 恰好包含K种不同整数的子区间 = 最多包含K种整数的子区间 - 最多包含K-1

  8. 多线程Tread中的常用方法

    多线程的方法 Tread中常用的方法 start():启动当前线程;调用当前线程的run() run():通常需要重写Thread类中的方法,将创建的线程要执行的操作声明在此方法中 currentThread():静态方法,返回执行当前代码的线程 getName():获取当前线程的名字 setName()

  9. [Python] 使用 NumPy 处理数组笔记

    目录 1. 使用 array() 函数创建数组 1.1 基础用法 1.2 array 的定义 1.3 dtype 参数 1.4 copy 参数 1.5 ndmin 参数 1.6 subok 参数 2. 创建等差数列 3. 创建随机数组 3.1 rand() 函数 3.2 randn()函数 3.3 randint()函数 4. NumPy 数组属性 4.1 ndarray.shape

  10. 【JavaScript】数组分组

    数组分组 最终期望实现 编写一个 chunk 函数,将数组拆分成多个 size 长度的块,并组成一个新数组。 如果数组无法被分割成全部等长的块,那么最后剩余的元素将组成一个块。 参数 array (Array) 需要被处理的数组 [size=0] (number) 每个块的长度 返回值(Arr

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词