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

小肸永久会员 2023年9月16日下午11:57

class Solution {
    //时间复杂度为O(nlog(N))
    //空间复杂度为O(N)
    //算法性能稳定
    static int[] tmp;
    static int res;
    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        res = 0;
        merge(nums, 0, nums.length - 1);
        return res;
    }
    private void merge(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        merge(nums, left, mid);
        merge(nums, mid + 1, right);
        //这里可以剪枝优化一下
        mergeSort(nums, left, mid, right);
    }
    private void mergeSort(int[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i ++) {
            tmp[i] = nums[i];
        }
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k ++) {
            if (i > mid) {
                nums[k] = tmp[j ++];
            } else if (j > right) {
                nums[k] = tmp[i ++];
            } else if (tmp[i] <= tmp[j]) {
                nums[k] = tmp[i ++];
            } else {
                //当tmp[i] > tmp[j]时，说明有(mid - i + 1个)逆序对，
                //比如L= {2，3}, R = {1, 4}就有2个逆向对，rPtr指向4时就没有逆序对产生
                nums[k] = tmp[j ++];
                res += (mid - i + 1);
            }
        }
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月14日下午2:40

思路：~~没有理解为什么可以用归并排序统计逆序对，看题解的代码逻辑倒是看得懂，就是不理解如果用归并分治了，不会有打乱顺序导致统计不对的问题吗？~~ 大概看明白了，整体是归并排序的思路，先分后治，在治的过程中统计逆序对的个数，[7,3,2,6,0,1,5,4]第一次治，[7,3]统计后再统计[3,7][2,6]，逐步向上就能保证与7相关的逆序对都统计出来，其他的数字同理。（代码中注释的地方就是有一边先遍历完另外的要已过去，然后新数组局部覆盖旧数组）
复杂度：时间复杂度O(nlogn)，空间复杂度O(n)

class Solution {
    int count;

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

    public void merge(int[] nums, int left, int right) {
        int mid = (right - left) / 2 + left;
        if (left < right) {
            merge(nums, left, mid);
            merge(nums, mid + 1, right);
            mergeSort(nums, left, right, mid);
        }
    }

    public void mergeSort(int[] nums, int left, int right, int mid) {
        int[] arr = new int[right - left + 1];
        int index = 0;
        int tmp1 = left, tmp2 = mid + 1;

        while (tmp1 <= mid && tmp2 <= right) {
            if (nums[tmp1] <= nums[tmp2]) {
                arr[index++] = nums[tmp1++];
            } else {// 统计逆序对的个数
                count += (mid - tmp1 + 1);
                arr[index++] = nums[tmp2++];
            }
        }

        // 把左侧剩余的数移到数组
        while (tmp1 <= mid) {
            arr[index++] = nums[tmp1++];
        }
        // 把右侧剩余的数移到数组
        while (tmp2 <= right) {
            arr[index++] = nums[tmp2++];
        }
        // 新数组中的数覆盖nums数组
        for (int k = 0; k < arr.length; k++) {
            nums[k + left] = arr[k];
        }
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月9日上午11:10

归并排序

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

    public 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;
    }

    public 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;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年9月9日上午12:58

归并排序，模板记一下

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

    public void merge(int[] nums, int left, int right){
        int mid = left + (right - left)/2;
        if(left < right){
            merge(nums, left, mid);
            merge(nums, mid+1, right);
            mergeSort(nums, left, mid, right);
        }
    }

    public void mergeSort(int[] nums, int left, int mid, int right){
        int[] temparr = new int[right-left+1];
        int index = 0;
        int temp1 = left, temp2 = mid+1;
        while(temp1 <= mid && temp2 <= right){
            if(nums[temp1] <= nums[temp2]){
                temparr[index++] = nums[temp1++];
            }else{
                count += (mid - temp1 + 1);
                temparr[index++] = nums[temp2++];
            }
        }
        while(temp1 <= mid){
            temparr[index++] = nums[temp1++];
        }
        while(temp2 <= right){
            temparr[index++] = nums[temp2++];
        }
        for(int i=0; i<temparr.length; i++){
            nums[i+left] = temparr[i];
        }
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年9月7日下午3:45

//思想1：冒泡排序，超时间了O(n^2)
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int res= 0;
        for(int i=nums.size()-1;i>=0;i--)
        {
            for(int j=0;j<i;++j)
            {
                if(nums[j]>nums[j+1])
                {
                    swap(nums[j],nums[j+1]);
                    ++res;
                }
            }
        }
        return res;
    }
};
//思想2：归并排序：时间O(nlogn),空间O(n)

class Solution {
public:
    int merge(vector<int>&nums,vector<int>&arr,int l,int mid,int r)
    {
        int count = 0;
        int i=l;
        int j = mid+1;
        int pos = l;
        while(i<=mid&&j<=r)
        {
            if(nums[i]>nums[j])
            {
                count+=(mid+1)-i;
                arr[pos++] = nums[j++];
            }
            else arr[pos++] = nums[i++];
        }
        while(i<=mid) arr[pos++]=nums[i++];
        while(j<=r) arr[pos++] = nums[j++];
        while(l<=r)
        {
            nums[l] = arr[l];
            ++l;
        }
        return count;
    }
    int mergeSort(vector<int>& nums,vector<int>& arr,int l,int r)
    {
        if(l>=r) return 0;
        int mid = (l+r)/2;
        int x1 = mergeSort(nums,arr,l,mid);
        int x2 = mergeSort(nums,arr,mid+1,r);
        int x3 = merge(nums,arr,l,mid,r);
        return x1+x2+x3;
    }
    int reversePairs(vector<int>& nums) {
        if(nums.size()<=1) return 0;
        vector<int> arr(nums.size());
        return mergeSort(nums,arr,0,nums.size()-1);

    }
};

0 赞同 0 条回复

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

共以下 5 个回答

# 回答此问题取消回复

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

共以下 5 个回答

# 回答此问题 取消回复

# 回答此问题取消回复