leetcode4题解

简介: leetcode4题解

LC4

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

算法的时间复杂度应该为 O(log (m+n))

class Solution {
   
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
   
        int m = nums1.size(), n = nums2.size(), k = 0, i = 0, j = 0;//把重复使用的数据用一个变量代替
        vector<int> sub(m + n, 0);
        while (i < m && j < n)
            sub[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        while (i < m) sub[k++] = nums1[i++];
        while (j < n) sub[k++] = nums2[j++];
        return k % 2 ? sub[k / 2] : (sub[k / 2] + sub[k / 2 - 1]) / 2.0; // 判断奇偶
    }
};//要会用a[i++]-->>a[i],i++;
目录
相关文章
|
6月前
leetcode-1447:最简分数
leetcode-1447:最简分数
46 0
|
6月前
leetcode-472. 连接词
leetcode-472. 连接词
49 0
|
3月前
|
算法
LeetCode第66题加一
LeetCode第66题"加一"的解题方法,通过遍历数组从后向前处理每一位的加法,并考虑进位情况,最终实现给定数字加一的功能。
LeetCode第66题加一
|
Python
LeetCode 1904. 你完成的完整对局数
一款新的在线电子游戏在近期发布,在该电子游戏中,以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。这意味着,在 HH:00、HH:15、HH:30 和 HH:45 ,将会开始一个新的对局,其中 HH 用一个从 00 到 23 的整数表示。游戏中使用 24 小时制的时钟 ,所以一天中最早的时间是 00:00 ,最晚的时间是 23:59 。
104 0
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
72 0
|
算法
LeetCode——944. 删列造序
LeetCode——944. 删列造序
107 0
|
算法
leetcode第47题
基本上都是在上道题的基础上改出来了,一些技巧也是经常遇到,比如先排序,然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据,然后再想办法还原。
leetcode第47题
|
存储
leetcode第57题
和上一道可以说是一个问题,只不过这个是给一个已经合并好的列表,然后给一个新的节点依据规则加入到合并好的列表。 解法一 对应 56 题的解法一,没看的话,可以先过去看一下。这个问题其实就是我们解法中的一个子问题没看的话,可以先过去看一下。这个问题其实就是我们解法中的一个子问题, 所以直接加过来就行了
leetcode第57题
leetcode第53题
解法一和解法二的动态规划,只是在定义的时候一个表示以 i 开头的子数组,一个表示以 i 结尾的子数组,却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和,不如解法二直接,只保存最大的和。
leetcode第53题