菜鸟笔记
提升您的技术认知

c 习题——数组中的逆序对-ag真人游戏

2023/3/22美团面试

题目

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例2:
输入:[1,2,3,4,5,6,7,0]
输出:7

时间复杂度要求控制在o(n logn),所以不能用两个for循环进行比较。
最简单的方法——归并。
归并排序我之前只是搞懂了原理没有怎么去实现,搞得我遇到这道题直接抓瞎了,md气死我了!
请同学们一定要多写代码。好记性不如烂笔头。

排序部分

int mergesort(vector& nums, int left, int right, vector& tmp)
    {
  
        if (left >= right) return 0;
        int mid = left   (right - left) / 2;
        int count = mergesort(nums, left, mid, tmp)   mergesort(nums, mid   1, right, tmp);//mid 1-right;//left-mid
        int i = left, j = mid   1, k = left;
        for (k = left; k <= right; k  )//至关重要,要更新tmp
        {
  
            tmp[k] = nums[k];
        }
        for (k = left; k <= right; k  )
        {
  
            if (i == mid   1)
            {
  
                nums[k]=tmp[j  ];
            }
            else if (j == right   1 || tmp[i] <= tmp[j])
            {
  
                nums[k]=tmp[i  ];
            }
            else
            {
  
                nums[k] = tmp[j  ];
                count  = (mid - i   1);
            }
        }
        return count;
    }

有的人喜欢搞两个函数,我觉得太麻烦了,这样子搞我更加直观。
原理图如下:

其实就是不断地二分,二分之后再二分知道编程一个元素一组,一个元素一组肯定是有序的呀,然后再两个两个比较,这里的两个两个是前后跨度为2的(如图所示),然后再四个四个比较(我就按双数来了,有可能是3,4个比较;4,5个比较,都可以,重在好理解!)然后再8,8个比较直到这个变成一个大组,这个大组都是有序的啦!

class solution {
  
public:
    //2023/3/22美团面试
    int mergesort(vector& nums, int left, int right, vector& tmp)
    {
  
        if (left >= right) return 0;
        int mid = left   (right - left) / 2;
        int count = mergesort(nums, left, mid, tmp)   mergesort(nums, mid   1, right, tmp);//mid 1-right;//left-mid
        int i = left, j = mid   1, k = left;
        for (k = left; k <= right; k  )//至关重要,要更新tmp
        {
  
            tmp[k] = nums[k];
        }
        for (k = left; k <= right; k  )
        {
  
            if (i == mid   1)
            {
  
                nums[k]=tmp[j  ];
            }
            else if (j == right   1 || tmp[i] <= tmp[j])
            {
  
                nums[k]=tmp[i  ];
            }
            else
            {
  
                nums[k] = tmp[j  ];
                count  = (mid - i   1);
            }
        }
        return count;
    }
    int reversepairs(vector& nums)
    {
  
        if (nums.size() < 2) return 0;
        vector tmp(nums.size());
        
        int c=mergesort(nums, 0, nums.size() - 1, tmp);
        
        return c;
    }
};
int main()
{
  
    solution a;
    vector nums = {
   7,5,6,4 };
    cout << a.reversepairs(nums) << endl;
    for (auto i : nums)
    {
  
        cout << i << ' ';
    }
    cout << endl;
    
    return 0;
}