九号球普通 2023年11月29日下午8:53

“`java
//没想出来
class Solution {
public int reversePairs(int[] record) {
//使用归并排序的思想
return mergeSort(record, 0, record.length – 1);
}

public int mergeSort(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;
}

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

}

0 赞同 0 条回复

招舟子普通 2023年9月8日下午8:16

class Solution {
public int reversePairs(int[] nums) {
return mergesort(nums,0,nums.length-1);
}
int mergesort(int[] nums,int left,int right){
if(left>=right){
return 0;
}
int mid = (left+right)/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(int[] nums,int l1,int r1,int l2,int r2){
int[] tmp = new int[r2-l1+1];
int i = l1,j=l2,count=0,k=0;
while(i<=r1&&j<=r2){
if(nums[i]>nums[j]){
count=count+(l2-i);
tmp[k++]=nums[j++];
}else{
tmp[k++]=nums[i++];
}
}
while(i<=r1){
tmp[k++]=nums[i++];
}
while(j<=r2){
tmp[k++]=nums[j++];
}
k=0;
for(i=l1;i<=r2;i++){
nums[i]=tmp[k++];
}
return count;
}
}
归并排序

0 赞同 0 条回复

BOZ 普通 2023年7月19日下午5:55

【思路】采用mergeSort的方法，每一次递归先统计左右两个子数组的逆序对数量，归并时再统计跨子树组的逆序对数量
【复杂度】时间复杂度O(nlogn)，空间复杂度O(n)

class Solution {
    std::vector<int> tmp;

    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;

        // optimization
        if (right - left == 1) {
            if (nums[left] > nums[right]) {
                std::swap(nums[left], nums[right]);
                return 1;
            } else return 0;
        }

        // sort left part and right part respectively
        int mid = (left + right) / 2;
        int result = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);

        // merge left and right part together
        int l = left, r = mid + 1, k = l;
        while(l <= mid || r <= right) {
            if (r > right || (l <= mid && nums[l] <= nums[r])) {
                result += r - (mid + 1);
                tmp[k++] = nums[l++];
            } else tmp[k++] = nums[r++];
        }
        for (k = left; k <= right; k++) nums[k] = tmp[k];
        return result;
    }
public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return mergeSort(nums, 0, nums.size() - 1);
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:47

“`C++
int mergeSort(vector& nums, vector& temp, int left, int right) {
// 递归终止条件：当子数组只包含一个元素时，无逆序对
if (left >= right) return 0;

int mid = left + (right - left) / 2;
int count = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right);

// 统计逆序对的数量
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
    if (nums[i] <= nums[j]) {
        temp[k++] = nums[i++];
    } else {
        temp[k++] = nums[j++];
        count += mid - i + 1; // 左边子数组 nums[i...mid] 的所有元素都大于 nums[j]
    }
}

// 将剩余的元素复制回原数组中
while (i <= mid) {
    temp[k++] = nums[i++];
}
while (j <= right) {
    temp[k++] = nums[j++];
}

// 将临时数组中排序好的部分复制回原数组
for (int m = left; m <= right; m++) {
    nums[m] = temp[m];
}

return count;

}

int reversePairs(vector& nums) {
int n = nums.size();
vector temp(n);
return mergeSort(nums, temp, 0, n – 1);
}

“`

0 赞同 0 条回复

张开怀普通 2023年7月16日下午9:51

class Solution{
public:
      int reversePairs(vector<int>& 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[i]);
                         j++;
                  }
                  for (int k =left; k<=right;k++){
                        nums[k] = temp[k - left];
                  }
                  return x1+x2+count;
            }
            return mergeSort(0, nums.size()-1);
      }

};

时间复杂度：O(nlogn)
空间复杂度：O(n)

0 赞同 0 条回复

Ming 普通 2023年7月16日下午4:04

归并排序，每合并时若右边大于左边，就会有l2-i个逆序对

public int reversePairs(int[] nums) {
        if(nums == null || nums.length <= 1) {
            return 0;
        }
        return mergeSort(nums, 0, nums.length - 1);
    }
    public int mergeSort(int[] nums, int l, int r) {
        if(l >= r) {
            return 0;
        }
        int mid = (r - l) / 2 + l;
        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[] temp = new int[r2 - l1 + 1];
        int k = 0;
        int count = 0;
        int i = l1;
        int j = l2;
        while(i <= r1 && j <= r2) {
            if(nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                count += l2 - i;
                temp[k++] = nums[j++];
            }
        }
        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 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月16日上午9:22

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0

        def mergeSort(left, right):
            if left >= right:
                return 0

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

            i, j = left, mid + 1
            count = 0

            while i <= mid and j <= right:
                if nums[i] > 2 * nums[j]:
                    count += mid - i + 1
                    j += 1
                else:
                    i += 1

            nums[left:right+1] = sorted(nums[left:right+1])
            return x1 + x2 + count


        return mergeSort(0, len(nums) - 1)

国际站

0 赞同 0 条回复

花老爷普通 2023年7月15日下午5:09

我也只会暴力，看官解

// 归并排序
public class Solution {
    public int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }

        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

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

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

            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }
}

0 赞同 0 条回复

Yodl. 普通 2023年7月15日下午2:27

//时间复杂度O(nlogn) 空间复杂度O(n)
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergeSort(0, nums.size() - 1, nums, tmp);
    }
private:
    int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];
        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 条回复

Vow the vow。普通 2023年7月15日下午12:20

只会暴力。还是得看题解

int res = 0;
    public int reversePairs(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return res;
    }

    private void mergeSort(int[] nums, int l, int r){
        if(l >= r) return;
        int mid = l + (r - l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1, r);
        merge(nums,l,mid,r);
    }

    private void merge(int[] nums, int l, int mid, int r){
        int i = l, j =  mid+1;
        int index = 0;
        int[] temp = new int[r-l+1];
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]){
                temp[index] = nums[i];
                i++; 
            }else{
                temp[index] = nums[j];
                j++;
                res += (mid -i + 1);  //[i,mid] 都大于j
            }
            index++;
        }
        while(i <= mid){
            temp[index++] = nums[i++];
        }
        while(j <= r){
            temp[index++] = nums[j++];
        }
        index = 0;
        while(index < temp.length){
            nums[l + index] = temp[index];
            index++;
        }
    }

0 赞同 0 条回复

yxy 普通 2023年7月14日下午9:43

时间复杂度O(nlogn)

const int N=5e4+10;
int tmp[N];

class Solution {
    int merge_sort(vector<int>& nums, int l, int r)
    {
        if(l>=r) return 0;
        int mid = l+r>>1, res = 0;
        res += merge_sort(nums, l, mid);

        res += merge_sort(nums, mid+1, r);
        int k = l;
        int i = l, j = mid+1;
        while(i<=mid&&j<=r)
        {
            if(nums[i]<=nums[j])
            {
                tmp[k++]=nums[i++];
            }
            else
            {
                tmp[k++]=nums[j++];
                res+=mid-i+1;
            }
        }
        while(i<=mid)
        {
            tmp[k++]=nums[i++];
        }
        while(j<=r)
        {
            tmp[k++]=nums[j++];
        }
        for(int i=l;i<=r;i++)
            nums[i]=tmp[i];
        return res;
    }
public:
    int reversePairs(vector<int>& nums) {
        return merge_sort(nums, 0, nums.size()-1);
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月14日下午5:21

class Solution {

    //思路：利用归并排序的思想
    //计算左半部分的逆序数
    //计算右半部分的逆序数
    //基于左右两边排好序的情况下，计算整体逆序数
    //3者相加，即为最终逆序数
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length == 0){
            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 leftCount = mergeSort(nums,left,mid);
        int rightCount = mergeSort(nums,mid + 1,right);
        int curCount = merge(nums,left,mid,mid+1,right);

        return leftCount + rightCount + curCount;
    }

    int merge(int[] nums,int leftStart,int leftEnd,int rightStart,int rightEnd){
        int count = 0;
        int[] temp = new int[rightEnd - leftStart + 1];
        int index = 0;
        int curLeft = leftStart;
        int curRight = rightStart;

        while(curLeft <= leftEnd && curRight <= rightEnd){
            if(nums[curRight] < nums[curLeft]){
                //右边小于左边
                //计算逆序数
                count = count + (leftEnd - curLeft) + 1;
                temp[index++] = nums[curRight++];
            }else{
                temp[index++] = nums[curLeft++];    //左边小，无逆序数
            }
        }

        while(curLeft <= leftEnd){
            temp[index++] = nums[curLeft++];
        }
        while(curRight <= rightEnd){
            temp[index++] = nums[curRight++];
        }

        //复制回去
        index = 0;
        for(int i = leftStart;i <= rightEnd;i++){
            nums[i] = temp[index++]; 
        }

        return count;
    }

}

0 赞同 0 条回复

Dsjh 普通 2023年7月14日下午3:58

MY

493 翻转对

class Solution {
public:
    int ans=0;
    int reversePairs(vector<int>& nums) {
        if(nums.size()<2){
            return 0;
        }
        ans = merge_sort(nums,0,nums.size()-1);
        return ans;
    }
    int merge_sort(vector<int>& nums,int l,int r){
        if(l>=r)
            return 0;
        int mid = l+(r-l)/2;
        int res1=merge_sort(nums,l,mid);
        int res2=merge_sort(nums,mid+1,r);
        int res = res1+res2;
        // 寻找逆序对
        int i=l,j=mid+1;
        while(i<=mid){
            while(j<=r && nums[i]>nums[j]){
                j++;
            }
            res += j-mid-1;
            i++;
        }
        // 归并
        vector<int> temp(r-l+1,0);
        i=l,j=mid+1;
        int k=0;
        while(i<=mid && j<=r){
            temp[k++] = nums[i]<nums[j] ? nums[i++]:nums[j++];
        }
        while(i<=mid)
            temp[k++] = nums[i++];
        while(j<=r)
            temp[k++] = nums[j++];
        k=0;
        for(int i=l;i<=r;i++){
            nums[i] = temp[k++];
        }
        return res;
    }
};

0 赞同 0 条回复

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

共以下 13 个回答

MY

# 回答此问题取消回复

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

共以下 13 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复