​LeetCode刷题实战493: 翻转对

共 2313字,需浏览 5分钟

 ·

2022-01-14 01:54

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 翻转对,我们先来看题面:
https://leetcode-cn.com/problems/reverse-pairs/

Given an integer array nums, return the number of reverse pairs in the array. A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

给定一个数组 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位整数的表示范围内。


解题

https://www.jianshu.com/p/6cc32f9e57c7

这道题可以采用归并排序 + 二分查找来解决。我们可以先考虑一个最简单的情况,如 [-10, -6],我们可以先将 [-10, -10] 分割为 L 和 R 两个子数组,其中 L = [-10], R = [-6]。显然,L 和 R 中都只有一个元素,本身就是有序数组,同时翻转对数为0。将 L 和 R 合并排序,由于 L[0] > 2 * R[0], 得到排序后的数组为 [-10, -6], 且翻转对数为 1。
上述过程大体上描绘了代码主体的框架,要求出一个数组的翻转对数,我们需要将其划分为 L 和 R,并求出 L 和 R 中的翻转对数 v1 和 v2,然后对排好序的 L 和 R 进行合并排序,得到翻转对数 v3,则数组本身的翻转对数就是 v1 + v2 + v3。

class Solution {
public:
    using ull = unsigned long long;
    static const int MAX = 50000;
    long long L[MAX / 2 + 2] = {0}, R[MAX / 2 + 2] = {0};
    ull Merge(vector<int>& nums, int left, int mid, int right){
        int L_end = mid - left;
        int R_end = right - mid;
        for(int i = 0;i < L_end;++i)
            L[i] = nums[left + i];
        for(int i = 0;i < R_end;++i)
            R[i] = nums[mid + i];
        L[L_end] = static_cast<long long>(numeric_limits<int>::max()) + 2;
        R[R_end] = static_cast<long long>(numeric_limits<int>::max()) + 2;
        ull cnt = 0;
        int i = 0, j = 0;
        for(int k = left;k < right;++k){
            if(L[i] < R[j]){
                nums[k] = L[i++];
            }else{
                if(R[j] < 0)
                    cnt += L_end - (upper_bound(L, L + L_end, R[j] * 2) - L);
                else
                    cnt += L_end - (upper_bound(L + i, L + L_end, R[j] * 2) - L);
                nums[k] = R[j++];
            }
        }
        return cnt;
    }
    int MergeSort(vector<int>& nums, int left, int right){
        ull v1 = 0, v2 = 0, v3 = 0;
        if(left + 1 < right){
            int mid = (left + right) >> 1;
            v1 = MergeSort(nums, left, mid);
            v2 = MergeSort(nums, mid, right);
            v3 = Merge(nums, left, mid, right);
        }
        return v1 + v2 + v3;
    }
    int reversePairs(vector<int>& nums) {
        return MergeSort(nums, 0, nums.size());
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:


LeetCode1-480题汇总,希望对你有点帮助!

LeetCode刷题实战481:神奇字符串

LeetCode刷题实战482:密钥格式化

LeetCode刷题实战483:最小好进制

LeetCode刷题实战484:寻找排列

LeetCode刷题实战485:最大连续 1 的个数

LeetCode刷题实战486:预测赢家

LeetCode刷题实战487:最大连续1的个数 II

LeetCode刷题实战488:祖玛游戏

LeetCode刷题实战489:扫地机器人

LeetCode刷题实战490:迷宫

LeetCode刷题实战491:递增子序列

LeetCode刷题实战492:构造矩形



浏览 17
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报