首页 > 其他分享 >leetcode 4. 寻找两个正序数组的中位数 困难 未完全解决

leetcode 4. 寻找两个正序数组的中位数 困难 未完全解决

时间:2024-11-12 16:44:12浏览次数:1  
标签:正序 数组 int 中位数 && leetcode

leetcode 4. 寻找两个正序数组的中位数

一、使用额外空间,类似归并排序的做法

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();int n = nums2.size();
        int temp[(m+n)/2+1];  //不需要用到(m+n)大小的数组,最多放一半多一点就能够确定结果
        //接下来的程序和归并排序中,两个有序数组合并特别像,不同之处在于这个只需要存到(m+n)/2+1
        int count = 0,i = 0,j = 0;
        while(i < m && j < n && count <= (m+n)/2){
            if(nums1[i] < nums2[j]){
                temp[count++] = nums1[i++];
            }
            else{
                temp[count++] = nums2[j++];
            }
        }
        while(i < m && count <= (m+n)/2)  temp[count++] = nums1[i++];
        while(j < n && count <= (m+n)/2)  temp[count++] = nums2[j++];
        if((m+n)%2==0) return (temp[(m+n)/2-1]*1.0+temp[(m+n)/2]*1.0)/2.0;
        else return temp[(m+n)/2]*1.0;
        
        /*//这是原本尝试不使用额外空间的代码,特别丑陋
        int m = nums1.size();int n = nums2.size();
        int count = 0,i = 0,j = 0;
        while(i < m && j < n && count < (m+n)/2){
            if(nums1[i] < nums2[j]) j++;
            else i++;
            count++;
        }
        if(count == (m+n)/2){
            if((m+n)%2==0){
                if(i == m){
                    int a = max(nums1[i-1],nums2[j]);
                    int b = nums2[j+1];
                    return (a*1.0+b*1.0)/2.0;
                }
                if(j == n){
                    int a = max(nums1[i],nums2[j-1]);
                    int b = nums2[i+1];
                    return (a*1.0+b*1.0)/2.0;
                }
                return (nums1[i]*1.0+nums2[j]*1.0)/2.0;             
            }
            else{
                if(nums1[i] < nums2[j]) j++;
                else i++;
                return max(nums1[i],nums2[j])*1.0;
            }
        }

        if(i < m){
            if((m+n)%2==0){
                while(count < (m+n)/2)  i++;
                return (nums1[i]*1.0+nums1[i+1]*1.0)/2.0;
            }
            else{
                while(count < (m+n)/2)  i++;
                return nums1[i+1]*1.0;
            }
        }
        if(j < m){
            if((m+n)%2==0){
                while(count < (m+n)/2)  j++;
                return (nums2[j]*1.0+nums2[j+1]*1.0)/2.0;
            }
            else{
                while(count < (m+n)/2)  j++;
                return nums2[j+1]*1.0;
            }
        }
        return 0;
        */
    }
};

二、枚举,利用单调数组的性质

 灵茶山艾府的通解

 

标签:正序,数组,int,中位数,&&,leetcode
From: https://www.cnblogs.com/uacs2024/p/18542206

相关文章

  • 代码随想录算法训练营第十一天|LeetCode150.逆波兰表达式求值、239.滑动窗口最大值、3
    前言打卡代码随想录算法训练营第49期第十一天 φ(゜▽゜*)♪首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。今日题目在学......
  • 代码随想录算法训练营第三天(LeetCode203.移除链表元素;LeetCode707.设计链表;LeetCode20
    LeetCode203.移除链表元素题目链接:LeetCode203.移除链表元素题目链接思路这道题目主要考察的是移除一个链表当中的元素,我们可以先在给定的链表前面加一个虚拟头结点,这样我们对给定链表头结点的操作和给定链表其余结点的操作就会变得相同。代码classSolution{p......
  • 代码随想录算法训练营第四天(LeetCode24.两两交换链表中的节点;LeetCode10.删除链表的倒
    LeetCode24.两两交换链表中的节点题目链接:两两交换链表中的节点题目链接思路这道题其实就是一个模拟题,要求每次交换链表中两个相邻的节点(1、2节点互换;3、4节点互换;2、3节点不互换,意思就是交换过的节点不参与后续的交换了),同时只能进行节点交换,不能进行值交换。主要考......
  • LeetCode【0011】盛最多水的容器
    本文目录1中文题目2求解思路2.1基础解法:暴力算法2.2优化解法:分治法2.3最优解法:双指针法3题目总结1中文题目给定一个长度为n的整数数组height。有n条垂线,第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线,使得它们与x轴共同构成的......
  • LeetCode【0010】正则表达式匹配
    本文目录1中文题目2求解思路2.1基础解法:递归法2.2优化解法:动态规划和递归结合2.3最优解法:NFA(非确定性有限自动机)3题目总结1中文题目给一个字符串s和一个字符规律p,实现一个支持‘.’和‘*’的正则表达式匹配。‘.’匹配任意单个字符‘*’匹配零个或......
  • leetcode算法题-有效的括号(简单)
    有效的括号(简单)leetcode:https://leetcode.cn/problems/valid-parentheses/description/前言防止脑袋生锈,做一下leetcode的简单算法题,难得也做不来哈哈。大佬绕道,小白可看。题目描述给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:......
  • leetcode刷题笔记--最大滑动窗口
    classSolution{publicintlongestOnes(int[]nums,intk){intl=0,r=0;while(r<nums.length){if(nums[r++]==0){k--;}if(k<0&&nums[l++]==0){......
  • 代码随想录算法训练营第二十二天| leetcode77. 组合、leetcode216.组合总和III、leetc
    1leetcode77.组合题目链接:77.组合-力扣(LeetCode)文章链接:代码随想录视频链接:带你学透回溯算法-组合问题(对应力扣题目:77.组合)|回溯法精讲!_哔哩哔哩_bilibili思路:开始想循环,感觉行不通,然后看了视频,就嗯理解了一些感觉跟递归的思路确实差不多1.1回溯三部曲回溯的方法首......
  • 算法:LeetCode448_找出所有数组中消失的数字_java实现
    packagecom.leetcode;importjava.util.*;/***LeetCode448FindDisappearedNumInArr:找出所有数组中消失的数字*/publicclassLeetCode448FindDisappearedNumInArr{/***方法1.hashset,找出没出现的数字*/publicstaticList<Integer>findD......
  • leetcode1008. 前序遍历构造二叉搜索树
    给定一个整数数组,它表示BST(即 二叉搜索树 )的 先序遍历 ,构造树并返回其根。保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。二叉搜索树 是一棵二叉树,其中每个节点, Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值......