剑指 Offer 51. 数组中的逆序对

Offer_51

题目描述

方法一：暴力法（双层循环，超时）

package com.walegarrett.offer;

/**

 * @Author WaleGarrett

 * @Date 2021/2/9 9:12

 */

/**

 * 题目详情：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

 * 输入一个数组，求出这个数组中的逆序对的总数。

 */

import java.util.Arrays;

/**

 * 方法一：暴力解法（超时TLE）

 */

public class Offer_51 {

    public int reversePairs(int[] nums) {

        int len = nums.length;

        int cnt = 0;

        for(int i=0; i<len; i++){

            int now = nums[i];

            for(int j=0;j<i;j++){

                if(nums[j] > now)

                    cnt++;

            }

        }

        return cnt;

    }

}

方法二：归并排序法

/**

 * 方法二：归并排序

 */

class Offer_51_2 {

    public int reversePairs(int[] nums) {

        int len = nums.length;

        if(len < 2)

            return 0;

        int[] second = Arrays.copyOf(nums, len);

        return reversePairs(nums, 0, len-1, new int[len]);

    }

    int reversePairs(int[] nums, int left, int right, int[] tmp){

        if(left == right)

            return 0;

        int mid = (left + right) >> 1;

        int leftCnt = reversePairs(nums, left, mid, tmp);

        int rightCnt = reversePairs(nums, mid+1, right, tmp);

        //左半部分的最大值小于右半部分的最小值，所以这两部分的和没有逆序数对

        if(nums[mid] <= nums[mid+1])

            return leftCnt + rightCnt;

        int crossCnt = mergeAndCount(nums, left, right, tmp);

        return leftCnt + rightCnt + crossCnt;

    }

    //合并并统计逆序数

    int mergeAndCount(int[] nums, int left, int right, int[] tmp){

        for(int i=left;i<=right;i++){

            tmp[i] = nums[i];

        }

        int mid = (left + right) >> 1;

        int cnt = 0;

        int i = left;

        int j = mid+1;

        for(int k=left; k<=right; k++){

            if(i == mid+1){

                nums[k] = tmp[j];

                j++;

            }else if(j == right+1){

                nums[k] = tmp[i];

                i++;

            }else if(tmp[i] <= tmp[j]){//左指针右移

                nums[k] = tmp[i];

                i++;

            }else{//右指针右移

                nums[k] = tmp[j];

                j++;

                cnt += (mid-i+1);

            }

        }

        return cnt;

    }

}

方法三：树状数组

/**

 * 方法三：树状数组

 */

//树状数组

class BIT{

    int[] tree;

    int n;

    public BIT(int n){

        this.n = n;

        this.tree = new int[n+1];

    }

    public static int lowbit(int x){

        return x&(-x);

    }

    public void update(int i){

        while(i<=n){

            ++ tree[i];

            i += lowbit(i);

        }

    }

    public int query(int i){

        int cnt = 0;

        while(i!=0){

            cnt += tree[i];

            i -= lowbit(i);

        }

        return cnt;

    }

}

class Offer_51_3 {

    public int reversePairs(int[] nums) {

        int len = nums.length;

        int[] tmp = new int[len];

        tmp = Arrays.copyOf(nums, len);

        //离散化：获取元素之间的相对排名

        Arrays.sort(tmp);

        for(int i=0; i<len; i++){

            nums[i] = Arrays.binarySearch(tmp, nums[i]) + 1;

        }

        BIT bit = new BIT(len);

        int ans = 0;

        for(int i = len-1; i>=0; i--){

            ans+=bit.query(nums[i] - 1);

            bit.update(nums[i]);

        }

        return ans;

    }

}

巴特西

剑指 Offer 51. 数组中的逆序对 + 归并排序 + 树状数组

剑指 Offer 51. 数组中的逆序对

Offer_51

题目描述

方法一：暴力法（双层循环，超时）

方法二：归并排序法

方法三：树状数组

参考题解：数组中的逆序对

最新文章

热门文章