Leetcode 面试题51. 数组中的逆序对 493. 翻转对

地址

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

https://leetcode-cn.com/problems/reverse-pairs/

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

 

示例 1:

输入: [7,5,6,4]
输出: 5
 

限制：

0 <= 数组长度 <= 50000

这是使用归并排序计算逆序对的裸题

class Solution {
public:
    int tmp[50010];
    int ans =0;
    void merge_sort(vector<int>& q, int l, int r)
{
    if (l >= r) return;

    int mid =( l + r) >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
   
    int i=l; int j =mid+1;
    while(i<=mid && j<=r){
        if(q[i] > q[j]){
            ans += mid-i+1;
            j++;
        }else{
            i++;
        }
    }
        

    int k = 0;
    i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
    
    int reversePairs(vector<int>& nums) {
         merge_sort(nums, 0, nums.size()-1);
       
        return ans;
    }
};

下一题

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2
示例 2:

输入: [2,4,3,5,1]
输出: 3
注意:

给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。

同上一题一样只不过判断从判断大小该为判断 n[i]>2*n[j]

class Solution {
public:
    int tmp[50010];
    int ans =0;
    void merge_sort(vector<int>& q, int l, int r)
{
    if (l >= r) return;

    int mid =( l + r) >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
   
    int i=l; int j =mid+1;
    while(i<=mid && j<=r){
        if((long long)q[i] > (long long )2*q[j]){
            ans += mid-i+1;
            j++;
        }else{
            i++;
        }
    }
        

    int k = 0;
    i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
    
    int reversePairs(vector<int>& nums) {
         merge_sort(nums, 0, nums.size()-1);
       
        return ans;
    }
};

Leetcode 面试题51. 数组中的逆序对 493. 翻转对

推荐阅读