【排序算法运用】剑指 Offer 51. 数组中的逆序对-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月17日下午3:44

归并排序的思想，不要忘记递归结束条件

class Solution {
    public int reversePairs(int[] nums) {
        //归并排序计算交换的次数。
        if(nums == null || nums.length <= 1) return 0;
        return sort(nums, 0, nums.length - 1);
    }
    int sort(int[] nums, int left, int right){
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        int x = sort(nums, left, mid);
        int y = sort(nums, mid + 1, right);
        int z = merge(nums, left, mid, right);
        return x + y + z;
    }
    int merge(int[] nums, int left, int mid, int right){
        int[] a = new int[right - left + 1];
        int l = left, r = mid + 1;
        int count = 0;
        //填充数组的逻辑走不通
        int i = 0;
        while(l <= mid && r <= right){
            if(nums[l] > nums[r]){
                count += mid - l + 1;
                a[i++] = nums[r++];
            }else{
                a[i++] = nums[l++];
            }
        }
        while(r <= right){
            a[i++] = nums[r++];
        }
        while(l <= mid){
            a[i++] = nums[l++];
        }
        for(i = 0; i < a.length; i++){
            nums[left + i] = a[i];
        }
        return count;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月16日下午8:16

def reversePairs(num):
    if not num or len(num) == 1:
        return 0
    left = 0
    right = len(num) - 1

    return mergeSort(num,left,right)

def mergeSort(arr,left,right):
    # 归并排序，在merge的过程计算逆序的数量
    if left >= right:
        return 0

    mid = (right - left) // 2 + left

    x1 = mergeSort(arr,left,mid)
    x2 = mergeSort(arr,mid+1,right)
    x3 = merge(arr,left,mid,mid+1,right)
    return x1 + x2 + x3
def merge(arr,l1,r1,l2,r2):
    i = l1
    j = l2
    l = []
    count = 0
    while i <= r1 and j <= r2:

        if arr[j] < arr[i]:
            # 说明当前j与[i:l2]之间的元素都可以组成逆序数组
            count += l2 - i
            l.append(arr[j])
            j += 1
        else:
            l.append(arr[i])
            i += 1


    while i <= r1:
        l.append(arr[i])
        i +=1

    while j <= r2:
        l.append(arr[j])
        j += 1

    # 把临时数组赋给数组
    k = 0
    for _ in range(l1,r2+1):
        arr[_] = l[k]
        k += 1

    return count

0 赞同 0 条回复

lucca 普通 2023年1月16日下午5:35

归并排序

时间复杂度O(NlogN)
空间复杂度O(N)

class Solution {
    public int reversePairs(int[] nums) {
        return sort(nums, 0, nums.length - 1);
    }

    private int sort(int[] a, int l, int r) {
        if (l >= r) return 0;

        int mid = l + r >> 1;
        int sum = sort(a, l, mid) + sort(a, mid + 1, r);

        int i = l, j = mid + 1;

        int[] tmp = new int[r - l + 1];
        int idx = 0;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) tmp[idx++] = a[i++];
            else {
                sum += (mid + 1 - i);
                tmp[idx++] = a[j++];
            }
        }
        while (i <= mid) tmp[idx++] = a[i++];
        while (j <= r) tmp[idx++] = a[j++];
        idx = 0;
        for (int k = l; k <= r; k++, idx++)
            a[k] = tmp[idx];
        return sum;
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年12月4日下午9:10

/**
     * 剑指 Offer 51. 数组中的逆序对
     */
    //时间复杂度O(nLgN) 归并使用来O(nLgn)
    //空间复杂度O(n)
    int[] nums,tmp;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return merge(0,nums.length-1);
    }
    private int merge(int left,int right){
        //终止条件
        if(right<=left) return 0;
        //递归划分
        int m =(left+right)/2;
        int res = merge(left,m)+merge(m+1,right);
        //合并阶段
        int i=left,j=m+1;
        for (int k = left; k <=right; k++) {
            tmp[k]=nums[k];
        }

        for (int k = left; k <=right; k++) {
            if(i==m+1){
                nums[k]=tmp[j++];
            }else if(j==right+1||tmp[i]<=tmp[j]){
                nums[k]=tmp[i++];
            }else {
                nums[k]=tmp[j++];
                res+=m-i+1;//统计逆序对
            }
        }
        return res;
    }

0 赞同 0 条回复

@ 普通 2022年12月3日上午10:34

思路：归并排序

时间复杂度：O(NlogN)

空间复杂度：O(N)

class Solution {

    private int res;

    public int reversePairs(int[] nums){
        rec(nums, 0 , nums.length - 1);

        return res;
    }

    public void rec(int[] ary, int l, int r){
        if(l >= r)
            return;

        int mid = l + (r - l) / 2;

        rec(ary, l, mid);
        rec(ary, mid + 1, r);

        if(ary[mid] > ary[mid + 1])
            merge(ary, l, mid, r);
    }

    private void merge(int[] arr, int l, int mid, int r) {
        int[] newArr = Arrays.copyOfRange(arr, l, r + 1);

        int i = 0, j = (mid + 1) - l;

        for (int k = l; k <= r; k++) {
            if(i > mid - l){
                arr[k] = newArr[j++];
            }
            else if(j > r -l){
                arr[k] = newArr[i++];
            }
            else if(newArr[i] <= newArr[j]){
                arr[k] = newArr[i];
                i++;
            } else{
                res += mid - l - i + 1;
                arr[k] = newArr[j];
                j++;
            }


        }
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:45

//归并排序
func reversePairs(nums []int) int {
    return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, start, end int) int {
    if start >= end {
        return 0
    }
    mid := start + (end - start)/2
    cnt := mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end) //cnt包括整体+左半+右半
    tmp := []int{}  //辅助数组,用于存储排好序的数
    i, j := start, mid + 1 //左指针从左半部分的左端开始遍历 右指针从右半部分的左端开始遍历
    for i <= mid && j <= end {  //指针超出自己的那部分则退出循环
        if nums[i] <= nums[j] { //当左元素小于等于右元素 说明在右半部分的右元素的左边的元素均小于左元素
            tmp = append(tmp, nums[i])
            cnt += j - (mid + 1)    //因此cnt需要加上右元素左边部分的元素数量
            i++
        } else {
            tmp = append(tmp, nums[j])  //当左元素大于右元素 不能直接开始计数 
            j++                         //因为不确定右元素右边还有没有比左元素更小的元素
        }
    }
    for ; i <= mid; i++ {   //处理另一半未遍历完的数据
        tmp = append(tmp, nums[i])
        cnt += end - (mid + 1) + 1
    }
    for ; j <= end; j++ {   //同上
        tmp = append(tmp, nums[j])
    }
    for i := start; i <= end; i++ { //将排序好的数组元素依次赋值给nums数组
        nums[i] = tmp[i - start]
    }
    return cnt
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日下午6:35

class Solution {
public:
    int count = 0;
    int reversePairs(vector<int>& nums) {
        mergesort(nums,0,nums.size()-1);
        return count;

    }

    void mergesort(vector<int> nums, int l, int r){
        if(l>=r) return;
        int mid = (l+r)/2;
        mergesort(nums,l,mid);
        mergesort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }

    void merge(vector<int>& nums,int l, int mid, int r){
        vector<int> tmp(r-l+1); 
        int i = l,j = mid+1;
        int pos = 0;//指向临时数组
        while(i<=mid && j<=r){ //两个数组都有元素
            if(nums[i]<=nums[j]){
                tmp[pos++] = nums[i++];
            }else{
                count += mid-i+1;
                tmp[pos++] = nums[j++];
            }
        }
        while(i<=mid) tmp[pos++] = nums[i++];
        while(j<=r) tmp[pos++] = nums[j++];
        for(int k = 0; k < tmp.size();k++){
            nums[l+k] = tmp[k];
        }        
    }
};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年12月1日下午3:41

标注① ②的方法都可以解决问题，此题类似翻转对，和计算右侧小于自身元素相同。于是采用两道题目的思想解答

class Solution {
    public int reversePairs(int[] nums) {
        if (nums.length == 0) return 0;
        sort(nums);
        return count;
    }
    int[] temp;
    public void sort(int[] nums) {
        int n = nums.length;
        temp = new int[n];
        sort(nums,0,n-1);
    }
    public void sort(int[] nums,int lo,int hi){
        if(lo == hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(nums,lo,mid);
        sort(nums,mid+1,hi);
        merge(nums,lo,mid,hi);
    }
    int count = 0;
    public void merge(int[]nums,int lo,int mid,int hi) {
        for(int i = lo;i <= hi;i++) {
            temp[i] = nums[i];
        }
        int end = mid + 1;
        //①
        // 进行效率优化，维护左闭右开区间 [mid+1, end) 中的元素乘 2 小于 nums[i]
        // 为什么 end 是开区间？因为这样的话可以保证初始区间 [mid+1, mid+1) 是一个空区间
        for(int i = lo;i <= mid;i++) {
            while(end <= hi && (long)nums[i] > (long)nums[end]) end++;
            count += end - (mid + 1);
        }
        int i = lo, j = mid + 1;
        for(int p = lo;p <= hi;p++) {
            if(i == mid + 1) {
                nums[p] = temp[j++];
            }else if (j == hi + 1){
                nums[p] = temp[i++];
                //② count += j - mid - 1;
            }else if(temp[i] > temp[j]) {
                nums[p] = temp[j++];
            }else {
                nums[p] = temp[i++];
                // count += j - mid  -1;
            }
        }
    } 
}

0 赞同 0 条回复

lobort 普通 2022年11月22日上午12:12

class Solution {
    public int reversePairs(int[] nums) {
        //归并思想，将数组分为左右 分别求出左数组和右数组的逆序对数并排序 在求左右合在一起时的逆序对
        //时间复杂度O(Nlogn)  空间复杂度O(N)
        if(nums == null || nums.length <= 1){
            return 0;
        }
        return mergeSort(nums, 0, nums.length - 1);
    }

     int mergeSort(int[] nums, int left, int right){
         if(left >= right){
            return 0;
        }
        // int mid = left + ((right - left) /2);
        int mid = (right - left) / 2 + left;
        int res1 = mergeSort(nums, left, mid);
        int res2 = mergeSort(nums, mid + 1, right);
        int res3 = merge(nums, left, mid, right);
        return res1 + res2 + res3;
    }

     int merge(int[] nums, int l, int m, int r){
        int[] help = new int[r - l + 1];
        int count = 0;
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while(p1 <= m && p2 <= r){
            //前面的数大于后面的 count加上后面全部 p2指针向后移
            if(nums[p1] > nums[p2]){
                count += (m - p1 + 1);
                help[i++] = nums[p2++];
            }else{
                //不大于的时候p1指针向后移
                help[i++] = nums[p1++];
            }
            // count += (nums[p1] > nums[p2]) ? (m - p1 + 1) : 0;
            // help[i++] = nums[p2++];
        }
        //当p1或者p2越界之后 如果还有指针没有到底 将后面的元素复制到help数组中 下面的wile最多☞执行一个
        while(p1 <= m){
            help[i++] = nums[p1++];
        }
        while(p2 <= r){
            help[i++] = nums[p2++];
        }
        //将排序后的数组重新复制给原数组
        i = 0;
        for(p1 = l; p1 <= r; p1++){
            nums[p1] = help[i++];
        }
        return count;
    }
}

0 赞同 0 条回复

派大星普通 2022年11月21日下午10:20

class Solution {
//使用归并排序的方法，将数组分成左右两部分，分别计算两部分的逆序对数量，最后加上左右两部分比较的逆序对
//时间复杂度O(nlogn)
//空间复杂度O(n)
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length == 1)return 0;
        int sum = mergeSort(nums,0,nums.length - 1);
        return sum;
    }

    public int mergeSort(int[] nums,int l,int r){
        if(l >= r)return 0;
        int mid = (l + r)/2;
        int x1 = mergeSort(nums,l,mid);
        int x2 = mergeSort(nums,mid + 1,r);
        int x3 = merge(nums,l,mid,mid + 1,r);
        return x1 + x2 + x3;
    }

    public int merge(int[] nums,int l1,int r1,int l2,int r2){
        int[] newnums = new int[r2 - l1 + 1]; 
        int begin = l1;
        int sum = 0;
        int index = 0;
        while(l1 <= r1 && l2 <= r2){
            if(nums[l1] <= nums[l2]){
                newnums[index++] = nums[l1++];
            }else {
                newnums[index] = nums[l2];
                sum += (r1 - l1 + 1);
                l2++;
                index++;
            }
        }
        while(l1 <= r1){
            newnums[index] = nums[l1];
            l1++;
            index++;
        }
        while(l2 <= r2){
            newnums[index] = nums[l2];
            l2++;
            index++;
        }
        for (int i = 0; i < newnums.length; i++) {
            nums[begin] = newnums[i];
            begin++;
        }

        return sum;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月20日下午5:26

C++
归并排序，不会做，看视频的方法
——————————————————
class Solution {
public:
int reversePairs(vector& nums) {
if(nums.size() <= 1) return 0;
return mergeSort(nums, 0, nums.size() – 1);
}

int mergeSort(vector<int>& nums, int left, int right) {
    if(left >= right) return 0;
    int mid = (right - left) / 2 + left;
    int x1 = mergeSort(nums, left, mid);
    int x2 = mergeSort(nums, mid + 1, right);
    int x3 = merge(nums, left, mid, mid+1, right);

    return x1+x2+x3;
}

int merge(vector<int>& nums, int l1, int r1, int l2, int r2) {
    vector<int> ans;
    int cnt = 0;
    int i = l1, j = l2, k = 0;
    while(i <= r1 && j <= r2) {
        if(nums[i] > nums[j]) {
            cnt = cnt + (l2 - i);
            ans.push_back(nums[j]);
            j++;
        }else{
            ans.push_back(nums[i]);
            i++;
        }
    }
    while(i <= r1) {
        ans.push_back(nums[i]);
        i++;
    }
    while(j <= r2) {
        ans.push_back(nums[j]);
        j++;
    }

    for(i = l1;i <= r2; i++) {
        nums[i] = ans[k++];
    }
    return cnt;
}

};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月19日下午2:03

二路归并法时间复杂度O（nlgn），空间复杂度为O（n）

class Solution {
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        return mergeSort(nums,0,nums.length - 1);
    }
    private int mergeSort(int[] nums,int left,int right){
        if(left >= right) return 0;
        int mid = left + (right - left)/2;
        int x1 = mergeSort(nums,left,mid);
        int x2 = mergeSort(nums,mid + 1,right);
        int x3 = merge(nums,left,mid,mid + 1,right);
        return x1 + x2 + x3;
    }
    private int merge(int[] nums,int l1,int r1,int l2,int r2){
        int[] temp = new int[r2 - l1 + 1];
        int i = l1;
        int j = l2;
        int k = 0;
        int count = 0;
        while(i <= r1&&j <= r2){
            if(nums[i] > nums[j]){
                count = count + l2 - i;
                temp[k++] = nums[j++];
            }else{
                temp[k++] = nums[i++];
            }
        }
        while(i <= r1) temp[k++] = nums[i++];
        while(j <= r2) temp[k++] = nums[j++];
        k = 0;
        for(i = l1; i <= r2; i++){
            nums[i] = temp[k++];
        }
        return count;
    }
}

0 赞同 1 条回复

西西弗斯的石头永久会员 @ 西西弗斯的石头 2022年11月19日下午2:08

冒泡排序，力扣没通过，时间复杂度O（n ^ 2）,空间复杂度为O（1）

登录以回复

So 普通 2022年11月19日下午1:57

class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        return mergeSort(nums, 0, nums.length - 1);
    }

    int mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (right - left) / 2 + left;
        int x1 = mergeSort(nums, left, mid);
        int x2 = mergeSort(nums, mid + 1, right);
        int x3 = merge(nums, left, mid, mid + 1, right);
        return x1 + x2 + x3;
    }

    int merge(int[] nums, int l1, int r1, int l2, int r2) {
        int[] temp = new int[r2 - l1 + 1];
        int count = 0;
        int i = l1, j = l2, k = 0;
        while (i <= r1 && j <= r2) {
            if (nums[i] > nums[j]) {
                count += l2 - i;
                temp[k++] = nums[j++];
            } else {
                temp[k++] = nums[i++];
            }
        }
        while (i <= r1) {
            temp[k++] = nums[i++];
        }
        while (j <= r2) {
            temp[k++] = nums[j++];
        }
        k = 0;
        for (i = l1; i <= r2; i++) {
            nums[i] = temp[k++];
        }
        return count;
    }
}

时间：O(nlogn)，空间：O(n)

0 赞同 0 条回复

just 普通 2022年11月19日下午12:07

//归并排序
class Solution {
public:
int ms(int l,int r,vector& s,vector& a){
if(l>=r) return 0;
int mid=l+(r-l)/2;
int res=ms(l,mid,s,a)+ms(mid+1,r,s,a);
int i=l,j=mid+1,cnt=l;
while(i<=mid&&j<=r){
if(s[j]<s[i]){
a[cnt++]=s[j++];
res+=mid-i+1;
}
else a[cnt++]=s[i++];
}
while(i<=mid) a[cnt++]=s[i++];
while(j<=r) a[cnt++]=s[j++];
for(int k=l;k<=r;++k) s[k]=a[k];
return res;
}
int reversePairs(vector& nums) {
int n=nums.size();
if(n0||n1) return 0;
vector a(n,0);
return ms(0,n-1,nums,a);

};

0 赞同 0 条回复

青木普通 2022年11月18日下午10:26

/**
    有点难理解，写的太妙了
    用分治的思想，分别对小区域进行排序，同时计数
    计数的方法有点妙，如果左大于右，则加上m-i+1，
    因为用来计数的小数组都是排好序的，因此如果i可以产生逆序，则后面都可

    时间O(nlogn)
    空间O(n)
 */

class Solution {
    int[] nums, tmp;

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

    public int mySort(int l, int r){
        if(l>=r) return 0;
        int m = (l+r) / 2;
        int res = mySort(l,m) + mySort(m+1, r);

        for(int k=l; k<=r; k++){
            tmp[k] = nums[k];
        }

        int i=l, j=m+1;
        for(int k=l; k<=r; k++){
            if(i == m+1){
                nums[k] = tmp[j++];
            }
            else if(j == r+1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }
            else{
                nums[k] = tmp[j++];
                res += m - i + 1;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

【排序算法运用】剑指 Offer 51. 数组中的逆序对

共以下 15 个回答

归并排序

# 回答此问题取消回复

【排序算法运用】剑指 Offer 51. 数组中的逆序对

共以下 15 个回答

归并排序

# 回答此问题 取消回复

# 回答此问题取消回复