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

hi 普通 2023年11月9日下午11:24

在归并排序的时候求出逆序对

class Solution {
public:
    int temp[50010];
    int res;

    int reversePairs(vector<int>& record) {

        return merge_sort(record, 0, record.size() - 1);
    }

    int merge_sort(vector<int>& record, int l, int r){
        if(l >= r) return 0;

        int mid = l + r >> 1;
        res = merge_sort(record, l, mid) + merge_sort(record, mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r){
            if(record[i] <= record[j]) temp[k++] = record[i++];
            else{
                temp[k++] = record[j++];
                res += mid - i + 1;
            }
        }
       //防止有一边还有数没循环完，直接加入temp数组
        while(i <= mid) temp[k++] = record[i++];
        while(j <= r) temp[k++] = record[j++];

        for(int i = l, j=0; i <= r; i++, j++) record[i] = temp[j];

        return res;
    }      
};

0 赞同 0 条回复

June 普通 2023年9月13日下午5:09

class Solution {
    public int reversePairs(int[] nums) {
        if (nums.length < 2)
            return 0;
        int n = nums.length;
        int[] copy = new int[n];
        for(int i=0;i<n;i++)
            copy[i] = nums[i];
        int[] tmp = new int[n];
        return mergeSort(copy,0,n-1,tmp);
    }

    public int mergeSort(int[] nums, int L,int R,int[] tmp)
    {
        if(L == R)
            return 0;
        int mid = L + (R - L) / 2;
        //System.out.print(L);
        int leftPairs = mergeSort(nums,L,mid,tmp);
        int rightPairs = mergeSort(nums,mid+1,R,tmp);

        if(nums[mid] <= nums[mid + 1])
            return leftPairs + rightPairs; //左子数组严格小于等于右子数组，合并过程中不会贡献逆序对
        return leftPairs + rightPairs + mergeCount(nums,L,mid,R,tmp);       
    }

    public int mergeCount(int[] nums,int L,int mid,int R,int[] tmp)
    {
        for(int i= L ; i <= R; i++)
        {
            tmp[i] = nums[i];
        }
        int i = L, j = mid + 1;
        int count = 0;
        for(int k = L ; k <= R; k++)
        {
            if(i == mid + 1)
            {
                nums[k] = tmp[j];
                j++;
            }
            else if(j == R + 1)
            {
                nums[k] = tmp[i];
                i++;
            }
            else if(tmp[i] <= tmp[j])
            {
                nums[k] = tmp[i];
                i++;
            }
            else
            {
                nums[k] = tmp[j];
                j++;
                count += (mid - i + 1); // 针对 tmp[j]来说，tmp[i]及以后的都和他构成逆序对
            }
        }
        return count;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年8月19日下午5:11

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        //归并排序,冒泡排序不满足时间要求
        if(nums.empty() || 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 = 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;
    }
    int merge(vector<int>&nums,int l1,int r1,int l2,int r2){
        vector<int> temp(r2 - l1 + 1);
        int count = 0;
        int i = l1,j = l2,k = 0;
        while(i <= r1 && j <= r2){
            if(nums[j] < nums[i]){
                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(int i = l1;i <= r2;i++){
            nums[i] = temp[k++];
        }
        return count;
    }
};

0 赞同 0 条回复

普通 2023年8月18日下午11:55

c++ 代码运用归并排序
class Solution {
public:
int reversePairs(vector& nums)
{
int temp[nums.size()];
return mergesort(0,nums.size()-1,nums,temp);
}
int mergesort(int l,int r,vector&nums,int temp[])
{
if(l>=r) return 0;//区间长度为一返回
int m=(l+r)/2;
int sum=mergesort(l,m,nums,temp)+mergesort(m+1,r,nums,temp);
for(int k=l;k<=r;k++)
{
temp[k]=nums[k];
}
int i=l,j=m+1;
for(int k=l;k<=r;k++)
{
if(im+1)
{
while(k<=r) nums[k++]=temp[j++];
}
else if(jr+1)
{
while(k<=r)
nums[k++]=temp[i++];
}
else if(temp[i]<=temp[j]) nums[k]=temp[i++];
else if(temp[i]>temp[j]) nums[k]=temp[j++],sum+=m-i+1;
}
return sum;
}

};

0 赞同 0 条回复

Mby 普通 2023年8月14日上午11:54

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 = 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 条回复

北辰普通 2023年8月8日下午5:57

class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length<2) 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 leftPairs = mergeSort(nums,left,mid);
        int rightPairs = mergeSort(nums,mid+1,right);
        if(nums[mid]<nums[mid+1]) return leftPairs+rightPairs;
        int mergePairs = merge(nums,left,mid,mid+1,right);

        return leftPairs + rightPairs + mergePairs;
    }

    private 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[j]<nums[i]) {
                //统计逆序对
                count = count+(r1-i+1);
                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(int l=l1;l<=r2;l++){
                nums[l] = temp[k++];
        }
        return count;
    }
}

0 赞同 0 条回复

#00456B 普通 2023年8月8日上午12:20

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        return mergeSort(nums, 0 ,nums.size() - 1);
    }

    int mergeSort(vector<int>& nums, int left, int right){
        //x1和x2分别表示mid左右两边的逆序对数量
        //x3是左右都排好序之后在整个数组中的逆序对数量
        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;
    }

    int merge(vector<int>& nums, int l1, int r1, int l2, int r2){
        //用一个临时数组来保存结果
        vector<int> temp;
        int count = 0;//记录逆序对数量
        int i = l1, j = l2;
        while(i <= r1 && j <= r2){
            if(nums[i] > nums[j]){
                //说明左半部分i之后的数字都可以和j这个数字组成逆序对
                count += (l2 - i);
                temp.push_back(nums[j++]);
            }
            else{
                temp.push_back(nums[i++]);
            }
        }
        //左右部分比较完之后，把每半个部分没遍历完的遍历完
        while(i <= r1) temp.push_back(nums[i++]);
        while(j <= r2) temp.push_back(nums[j++]);

        // for(auto x:nums){
        //     cout<<x<<' ';
        // }
        // cout<<endl;
        // for(auto x: temp){
        //     cout<<x<<' ';
        // }
        // cout<<endl;
        //把临时数组复制回原数组
        for(i = l1; i <= r2; i++){
            nums[i] = temp[i];//l1可能是哪个子问题的左边界，i-l1是整个和nums一样大的数组的左边界
            // cout<<"i:"<<i<<" i-l1:"<<i-l1<<endl;
        }
        // for(auto x:nums){
        //     cout<<x<<' ';
        // }
        // cout<<endl;
        // cout<<endl;
        return count;
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年8月4日下午5:31

class Solution {
int result = 0;
public int reversePairs(int[] nums) {
//可以归并排序找出逆序数先分左右最后排序
qiege(nums,0,nums.length-1);
return result;
}
public void qiege(int []nums,int left,int right)
{
if(left<right)
{
int mid =(left+right)/2;
qiege(nums,left,mid);
qiege(nums,mid+1,right);
paixu(nums,left,right);
}
}
public void paixu(int []nums,int left,int right)
{
int mid =(left+right)/2;
int rightmid = mid+1;
int leftmid =left;
int temp =0;
int a[]=new int [right-left+1];
int i=0;
while(leftmid<=mid&&rightmid<=right)
{
if(nums[leftmid]<=nums[rightmid])
{
a[i++]=nums[leftmid++];

       }else
       {
           result =result +mid-leftmid+1;
           a[i++]=nums[rightmid++];

       }

   }
    while(leftmid<=mid)
    {
        a[i++]=nums[leftmid++];
    }
    while(rightmid<=right)
    {
        a[i++]=nums[rightmid++];
    }
    for(int j=0;j<a.length;j++)
    {
        nums[left+j]=a[j];
    }
}

}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月2日下午11:13

8.1
Day23：下面是代码

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        this.count = 0;
        mergeSort(nums, 0, nums.length-1);
        return count;
    }
    public void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;
        int mid = left + (right - left) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    public void merge(int[] nums, int left, int mid, int right){
        int tmp[] = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int t = 0; //指向临时数组的第一个元素
        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                tmp[t++] = nums[i++];
            }else{
                count += mid - i + 1;
                tmp[t++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[t++] = nums[i++];
        }
        while(j <= right){
            tmp[t++] = nums[j++];
        }
        for(int k = 0; k < tmp.length; k++){
            nums[left + k] = tmp[k];
        }
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年8月2日上午11:44

归并排序的应用

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

    public int mergeSort(int[] nums, int[] tmp, int l, int r) {
        if(l >= r) return 0;
        int mid = l + r >> 1;
        int i = l, j = mid + 1, k = 0;
        int res = mergeSort(nums,tmp,l,mid) + mergeSort(nums,tmp,mid + 1,r);
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j]) {
                tmp[k ++] = nums[i++];
            } else {
                res += mid - i + 1;
                tmp[k ++] = nums[j ++];
            }
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= r) tmp[k++] = nums[j++];

        for(int a = l,b = 0; a <= r; a++, b++){
            nums[a] = tmp[b];
        }   
        return res;
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月1日下午8:01

class Solution {
    int[] temp;
    int count;//累计逆序对的个数
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        temp = new int[nums.length];
        meargeSort(nums, 0, nums.length - 1);

        return count;
    }

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

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

        meargeSort(nums, l, mid);
        meargeSort(nums, mid + 1, r);

        mearge(nums, l, mid, r);
    }

    public void mearge(int[] nums, int l, int mid, int r){
        for(int i = l; i <= r; i++){
            temp[i] = nums[i];
        }

        int i = l;
        int j = mid + 1;

        //当nums[j] < nums[i]，因为区间[i, mid]左边有序（递增），所以nums[j]小于[i, mid]所有的数
        for(int k = l; k <= r; k++){
            if(i == mid + 1){
                nums[k] = temp[j++];
            }else if(j == r + 1){
                nums[k] = temp[i++];
            }else if(temp[i] <= temp[j]){
                nums[k] = temp[i++];
            }else{
                nums[k] = temp[j++];
                count += mid - i + 1;
            }
        }
    }
}

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复