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

扣子普通 2024年4月6日下午10:07

java
class Solution{
int[] record, tmp;
public int reversePairs(int[] record){
this.record = record;
tmp = new int[record.length];
return mergeSort(0, record.length – 1);
}
private int mergeSort(int l, int r){
if(l >= r) return 0;
int m = (l + r) / 2;
int res = mergeSort(l, m) + mergeSort(m + 1, r);
int i = l, j = m + 1;
for(int k = l; k <= r; k++){
tmp[k] = record[k];
}
for(int k = l; k <= r; k++){
if(i m + 1)
record[k] = tmp[j++];
else if(j r + 1 || tmp[i] <= tmp[j])
record[k] = tmp[i++];
else{
record[k] = tmp[j++];
res += m – i + 1;
}
}
return res;
}
}
提交

0 赞同 0 条回复

神经蛙普通 2024年3月30日下午10:49

class Solution {
public:
int reversePairs(vector& nums) {
if (nums.empty() || nums.size() <= 1)
return 0;

    function<int(int, int)> mergeSort;
    mergeSort = [&](int left, int right) -> int {
        if (left >= right)
            return 0;

        int mid = left + (right - left) / 2;
        int x1 = mergeSort(left, mid);
        int x2 = mergeSort(mid + 1, right);

        int i = left, j = mid + 1;
        int count = 0;
        vector<int> temp;

        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                count += mid - i + 1;
                temp.push_back(nums[j]);
                j++;
            } else {
                temp.push_back(nums[i]);
                i++;
            }
        }

        while (i <= mid) {
            temp.push_back(nums[i]);
            i++;
        }

        while (j <= right) {
            temp.push_back(nums[j]);
            j++;
        }

        for (int k = left; k <= right; k++) {
            nums[k] = temp[k - left];// temp 从0开始
        }

        return x1 + x2 + count;
    };

    return mergeSort(0, nums.size() - 1);
}

};
打卡

0 赞同 0 条回复

言之命至普通 2024年3月30日上午9:53

class Solution {
    int[] record, tmp;
    public int reversePairs(int[] record) {
        this.record = record;
        tmp = new int[record.length];
        return mergeSort(0, record.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = record[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                record[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                record[k] = tmp[i++];
            else {
                record[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
}

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

0 赞同 0 条回复

紫芝普通 2024年3月29日下午4:48

思路：归并排序

“`c++
class Solution {
public:
int reversePairs(vector& record) {
vector tmp(record.size());
return mergeSort(record, tmp, 0, record.size()-1);
}

private:
int mergeSort(vector&record, vector&tmp, int left, int right) {
if (left >= right) return 0;
// recursion division
int mid = left + (right – left) / 2;
int res = mergeSort(record, tmp, left, mid) + mergeSort(record, tmp, mid+1, right);
// merge
// save old value
for (int i=left; i<=right; i++) {
tmp[i] = record[i];
}
// do merge
int l = left, r = mid + 1;
for (int i=left; i<=right; i++) {
if (l mid+1) {
record[i] = tmp[r++];
} else if (r right+1 || tmp[l] <= tmp[r]) {
record[i] = tmp[l++];
} else {
res += mid – l + 1;
record[i] = tmp[r++];
}
}
return res;
}
};

“`

0 赞同 0 条回复

heathhou 普通 2024年3月27日下午10:43

class Solution {
public:
    int reversePairs(vector<int>& record) {
        if(record.empty() || record.size() <= 1){
            return {};
        }

        function<int(int, int)> mergeSort;
        mergeSort = [&](int left, int right) -> int {
            if(left >= right){
                return 0;
            }

            int mid = left + (right - left) / 2;
            int x1 = mergeSort(left, mid);
            int x2 = mergeSort(mid + 1, right);

            int i = left, j = mid + 1;
            int count = 0;
            vector<int> temp;

            while(i <= mid && j <= right){
                if(record[i] > record[j]){
                    temp.push_back(record[j++]);
                    count += mid - i + 1;
                }else{
                    temp.push_back(record[i++]);
                }
            }

            while(i <= mid){
                temp.push_back(record[i++]);
            }
            while(j <= right){
                temp.push_back(record[j++]);
            }

            for(int k = left; k <= right; ++k){
                record[k] = temp[k - left];
            }

            return x1 + x2 + count;
        };

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

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

0 赞同 0 条回复

云无深雁影普通 2024年3月27日下午8:40

class Solution {
int count = 0;
public int reversePairs(int[] record) {
mergeSort(0,record.length-1,record);
return count;

}

private void mergeSort(int l, int r,int[] record){
    if(l >= r) return;
    int mid = (l + r) / 2;
    //分
    mergeSort(l, mid, record);
    mergeSort(mid + 1, r, record);
    //并
    int[] temp = new int[r-l+1];
    int ptr = 0;
    int lptr = l;
    int rptr = mid + 1; 
    while(rptr <= r && lptr <= mid){
        if(record[lptr] <= record[rptr]){
            temp[ptr++] = record[lptr++];
        }else{
            temp[ptr++] = record[rptr++];
            count += mid - lptr + 1;                
        }
    }
    while(lptr<=mid){
        temp[ptr++] = record[lptr++];
    }
    while(rptr <= r){
        temp[ptr++] = record[rptr++];
    }
    for(int i = 0; i < temp.length; i++){
        record[i+l] = temp[i];
    }
}

}
//归并排序时间复杂度Onlogn 空间复杂度On

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月27日下午3:28

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

Jimmy 普通 2024年3月27日下午2:50

时间复杂度O(nlogn)，空间复杂度O(n)，归并排序

class Solution {
public:
    int reversePairs(vector<int>& record) {
        if(record.size() <= 1)
        {
            return 0;
        }
        return mergeSort(record,0,record.size()-1);
    }
    int mergeSort(vector<int>& record,int left,int right)
    {
        if(left >= right)
        {
            return 0;
        }
        int mid = left + (right-left)/2;
        int x1 = mergeSort(record,left,mid);
        int x2 = mergeSort(record,mid+1,right);
        int x3 = merge(record,left,mid,mid+1,right);

        return x1+x2+x3;
    }

    int merge(vector<int>& record,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(record[i] > record[j])
            {
                count = count + (l2-i);
                temp[k++] = record[j++];                
            }
            else
            {
                temp[k++] = record[i++];
            }
        }

        while(i<=r1)temp[k++] = record[i++];
        while(j<=r2)temp[k++] = record[j++];

        k = 0;
        for(i = l1;i<=r2;i++)
        {
            record[i] = temp[k++];
        }
        return count;

    }
};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月27日上午9:34

打卡

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

    int mergeSort(int l, int r, vector<int>& record) {
        if(l >= r) return 0;
        int mid = l + (r - l) / 2;
        int res = mergeSort(l, mid, record) + mergeSort(mid + 1, r, record);

        int i = l, j = mid + 1;
        int k = 0, tmp[r - l + 1];
        // 此时record的l~mid和mid+1~r这两个区间已经各自排序好了
        while(i <= mid && j <= r) {
            if(record[i] <= record[j]) tmp[k++] = record[i++];
            else {
                //此时record[i] > record[j]是一个逆序对
                //但由于左子区间已经按从小到大排好序
                //所以可推断出record[i]~record[m]都大于record[j]，这也是这个方法的巧妙之处
                //也就是说，在合并左右子区间时，新引入了共m-i+1对 以record[j]为右元素的逆序对
                tmp[k++] = record[j++];
                res += mid - i + 1;
            }
        }
        while(i <= mid) tmp[k++] = record[i++];
        while(j <= r) tmp[k++] = record[j++];
        for(k = 0, i = l; i <= r; k++, i++) record[i] = tmp[k];
        return res;
    }
};
/*
9 7 5 4 6
*/

0 赞同 0 条回复

Raphtalia. 普通 2024年3月26日下午10:04

class Solution {
public:
int reversePairs(vector& record) {
vector tmp(record.size());
return mergeSort(0, record.size() – 1, record, tmp);
}
private:
int mergeSort(int l, int r, vector& record, vector& tmp) {
// 终止条件
if (l >= r) return 0;
// 递归划分
int m = (l + r) / 2;
int res = mergeSort(l, m, record, tmp) + mergeSort(m + 1, r, record, tmp);
// 合并阶段
int i = l, j = m + 1;
for(int k = l; k <= r; k ++) {
tmp[k] = record[k];
}
int k = l;
while(i <= m && j <= r) {
if(tmp[i] <= tmp[j]) record[k ++] = tmp[i ++];
else {
res += m – i + 1;
record[k ++] = tmp[j ++];
}
}
while(i <= m) record[k ++] = tmp[i ++];
while(j <= r) record[k ++] = tmp[j ++];
return res;
}
};

0 赞同 0 条回复

王位詮釋普通 2024年3月26日下午8:43

class Solution {
    public int reversePairs(int[] record) {
        if(record==null||record.length<=1){
            return 0;
        }
        return mergeSort(record,0,record.length-1);
    }
    public int mergeSort(int[] record,int l,int r){
        if(l>=r){
            return 0;
        }
        int mid = l+(r-l)/2;
        int res = mergeSort(record,l,mid)+mergeSort(record,mid+1,r);
        int[] temp = new int[r-l+1];
        int i = l;
        int j = mid+1;
        int index = 0;
        while(i<=mid&&j<=r){
            if(record[i]>record[j]){//出现逆序对
                res+=(mid+1-i);
                temp[index++] = record[j++];
            }else{
                temp[index++] = record[i++];
            }
        }
        while(i<=mid){
            temp[index++] = record[i++];
        }
        while(j<=r){
            temp[index++] = record[j++];
        }
        //把原数组复制会原数组
        int k = 0;
        for(i=l;i<=r;i++){
            record[i] = temp[k++];
        }
        return res;
    }
}
思路：最开始是想冒泡排序做的，时间复杂度为O(n2)，后面数组长度大了之后超时了，所以得用归并排序，因为归并排序在merge的时候左右两个数组已经是排序过的，所以如果出现左边 比右边大了，那肯定就出现逆序对了，这个时候就应该mid+1-i，这个值就是这次的逆序，时间复杂度:O(nlogn)

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复