【LeetCode】剑指 Offer(26)

这篇具有很好参考价值的文章主要介绍了【LeetCode】剑指 Offer(26)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode)

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode)

【LeetCode】剑指 Offer(26)

题目的接口:

class Solution {
public:
    int reversePairs(vector<int>& nums) {

    }
};

解题思路:

这一道题,我的思路是用双指针暴力求解,

但这个数组长度,O(N^2)的时间复杂度肯定是不可能把所有样例跑完,

看了大佬的思路,用的是归并排序,(如果不会归并排序,最好先去学一下)

我一开始看了很久没有搞明白为什么,

实际上,这个思路是利用的归并排序的一个特性,具体思路如下:

例: 数组 [ 7, 5, 2, 6, 0, 1, 5, 4 ]

我们就拿这个数组归并到最后一步的时候作为样例:

[ 2, 5, 6, 7 ] 和 [ 0, 1, 4, 5 ]

由于他们通过先前的归并已经是两个有序的数组,

而最后一步就两个数组每个元素比大小,然后尾插到临时数组上,最后再拷贝回来,

重点来了:

第一个数比大小 2 > 0 所以尾插 0 并让第二个数组的下标begin2++,

因为这两个是升序数组,2 > 0,也表明 2 之后的所有数都大于 0 ,

那么这里就有 4 ( mid + 1,也就是第一个数组的长度) 个逆序数对,

那么,当 2 和 4 比较,2 < 4 ,就尾插 2 进临时数组,让第一个数组下标begin1++,

这个时候,继续往下比较,5 > 4, 尾插 4 并让第二个数组的下标begin2++,

因为这两个是升序数组,5 > 4,也表明 5 之后的所有数都大于 4,

但是因为第一个数组已经是第二个数了,所以:

这里就有 3 ( mid + 1 - begin1 (也就是减去第一个数组的下标))个逆序数对。

综上所述,

我们只需要在第一个数组的值 > 第二个数组的值的时候,记录逆序数对 (mid + 1 - begin1) 即可。

下面是代码:

代码:

class Solution {
public:
    //计数
    int res = 0;
    int reversePairs(vector<int>& nums) {
        //创建临时数组
        vector<int> tmp(nums.size());
        //归并排序,我用的是我学的归并排序模板
        merge_sort(nums, tmp, 0, nums.size() - 1);
        return res;
    }
private:
    void merge_sort(vector<int>& nums, vector<int>& tmp, int begin, int end) {
        if(begin >= end) return; //返回

        //分治
        int mid = (begin + end) >> 1;
        merge_sort(nums, tmp, begin, mid);
        merge_sort(nums, tmp, mid + 1, end);
        //[begin][mid], [mid + 1][end]

        //两个数组的下标
        int begin1 = begin, end1 = mid;
        int begin2 = mid + 1, end2 = end;

        //临时数组的下标
        int i = begin;

        //比较大小之后尾插进临时数组
        while(begin1 <= end1 && begin2 <= end2) {
            if(nums[begin1] <= nums[begin2]) {
                tmp[i++] = nums[begin1++];
            }
            else {
                tmp[i++] = nums[begin2++];
                //计算这一段的逆序数对数量//具体推导看文章的文字
                res += mid + 1 - begin1; //整个思路的核心
            }
        }

        //将没有插完的值全部尾插进临时数组
        while(begin1 <= end1) tmp[i++] = nums[begin1++];
        while(begin2 <= end2) tmp[i++] = nums[begin2++];

        //将临时数组拷贝回原数组
        for(int i = begin; i <= end; i++) {
            nums[i] = tmp[i];
        }
    }
};

过啦!!!

【LeetCode】剑指 Offer(26) 

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看文章来源地址https://www.toymoban.com/news/detail-410426.html

到了这里,关于【LeetCode】剑指 Offer(26)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (数组与矩阵) 剑指 Offer 03. 数组中重复的数字 ——【Leetcode每日一题】

    难度:简单 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入 : [2, 3, 1, 0, 2, 5, 3] 输出 :2 或

    2024年02月16日
    浏览(38)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(39)
  • (排序) 剑指 Offer 51. 数组中的逆序对 ——【Leetcode每日一题】

    难度:困难 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制 : 0 = 数组长度 = 50000 💡思路:归并排序 预备知识 「 归并排序 」是用 分治 思想,分

    2024年02月11日
    浏览(44)
  • (排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】

    难度:中等 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 提示 : 0 nums.length = 100 说明: 输出结果可能非常大,所以你需要返回一个字符串而不

    2024年02月10日
    浏览(48)
  • Leetcode-每日一题【剑指 Offer II 010. 和为 k 的子数组】

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况 示例 2: 输入: nums = [1,2,3], k = 3 输出: 2 提示: 1 = nums.length = 2 * 104 1000 = nums[i] = 1000 107 = k = 107 前置知识 前缀和

    2024年02月15日
    浏览(46)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(49)
  • (排序) 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 ——【Leetcode每日一题】

    难度:简单 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。 示例: 输入:nums = [1,2,3,4] 输出:[1,3,2,4] 注:[3,1,2,4] 也是正确的答案之一。 提示 : 0 = n u m s . l e n g t h = 50000 0 = nums.length = 50000 0 =

    2024年02月12日
    浏览(45)
  • 每天一道leetcode:剑指 Offer 53 - I. 在排序数组中查找数字 I(适合初学者&二分查找)

    统计一个数字在排序数组中出现的次数。 0 = nums.length = 10^5 -10^9 = nums[i] = 10^9 nums 是一个非递减数组 -10^9 = target = 10^9 使用两次二分查找找到target在数组中的左右边界,然后长度就是右边界减去左边界再加一,最后返回长度即可。   欢迎大家在评论区讨论,如有不懂的代码部分

    2024年02月14日
    浏览(53)
  • 剑指 Offer 66. 构建乘积数组

    给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1] 。不能使用除法。 示例: 提示: 所有元素乘积之和不会溢出 32 位整数 a.length = 100000 解答

    2024年02月16日
    浏览(49)
  • 【剑指offer】数据结构——数组

    【剑指offer】03.数组中重复的数字 //03. 数组中重复的数字 // 找出数组中重复的数字。 // 力扣 // 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。 // 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每 // 个数字重复了几次。请找出数组中任意一

    2024年02月08日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包