LeetCode实战：寻找两个有序数组的中位数
题目英文
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]The median is (2 + 3)/2 = 2.5
题目中文
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
算法实现
实现方式一：
public class Solution {public double FindMedianSortedArrays(int[] nums1, int[] nums2) {int len1 = nums1.Length;int len2 = nums2.Length;int len = len1 + len2;int[] nums = new int[len];Array.Copy(nums1, nums, len1);Array.Copy(nums2, 0, nums, len1, len2);Array.Sort(nums);if (len%2 == 0){return (nums[len/2] + nums[len/2 - 1])*0.5;}return nums[len/2]; }
}
实现方式二：
由于题目要求时间复杂度为 O(log(m + n))，所以不能从两个有序数组的首尾挨个遍历来找到中位数（复杂度 O(m + n)）；而是要通过二分策略，通过每次比较，能够直接按比例的刷掉一组数字，最后找到中位数（复杂度 O(log(m + n))）。
中位数：用来将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
nums1: [a1,a2,a3,...am]
nums2: [b1,b2,b3,...bn][nums1[:i],nums2[:j] | nums1[i:], nums2[j:]]nums1 取 i 个数的左半边
nums2 取 j = (m+n+1)/2 - i 的左半边
只要保证左右两边 个数 相同，中位数就在 | 这个边界旁边产生，从而可以利用二分法找到合适的 i。
public class Solution {public double FindMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.Length;int n = nums2.Length;if (m > n)return FindMedianSortedArrays(nums2, nums1);int k = (m + n + 1)/2;int left = 0;int right = m;while (left < right){int i = (left + right)/2;int j = k - i;if (nums1[i] < nums2[j - 1])left = i + 1;elseright = i;}int m1 = left;int m2 = k - left;int c1 = Math.Max(m1 == 0 ? int.MinValue : nums1[m1 - 1],m2 == 0 ? int.MinValue : nums2[m2 - 1]);if ((m + n)%2 == 1)return c1;int c2 = Math.Min(m1 == m ? int.MaxValue : nums1[m1],m2 == n ? int.MaxValue : nums2[m2]);return (c1 + c2)*0.5; }
}
实验结果
实现方式一：
- 状态：通过
- 2085 / 2085 个通过测试用例
- 执行用时: 188 ms, 在所有 C# 提交中击败了 72.14% 的用户
- 内存消耗: 26.9 MB, 在所有 C# 提交中击败了 5.05% 的用户
实现方式二：
- 状态：通过
- 2085 / 2085 个通过测试用例
- 执行用时: 160 ms, 在所有 C# 提交中击败了 99.18% 的用户
- 内存消耗: 26.8 MB, 在所有 C# 提交中击败了 5.05% 的用户
相关图文：
- LeetCode实战：两数之和
- LeetCode实战：三数之和
- LeetCode实战：缺失的第一个正数
- LeetCode实战：求众数
- LeetCode实战：快乐数
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
- LeetCode实战：设计循环双端队列
- LeetCode实战：爬楼梯
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
- LeetCode实战：搜索二维矩阵
- LeetCode实战：x 的平方根
相关文章：
从Preact了解一个类React的框架是怎么实现的(一): 元素创建
首先欢迎大家关注我的掘金账号和Github博客，也算是对我的一点鼓励，毕竟写东西没法获得变现，能坚持下去也是靠的是自己的热情和大家的鼓励。 之前分享过几篇关于React的文章: React技术内幕: key带来了什么React技术内幕: setState的秘密其…
呵呵，哈哈，嘿嘿，从今天起就开始写博客文了
第一篇嘛，完完全全的水篇，因为确实不知道该写些什么好啦，恩，哈，以后就多写一些的了，嘘，玩别的去了！拜拜！转载于:https://www.cnblogs.com/thinkgao/archive/2011/04/26/2…
UI设计培训怎么选择就业方向
相信大部分人学习UI设计就是为了找到一份不错的工作，那么UI设计培训怎么选择就业方向呢?UI设计师有哪些就业方向选择呢?来看看下面的详细介绍吧。 UI设计培训怎么选择就业方向? 图形设计：图形设计不仅仅是美术的设计。在UI设计的工作中，图…
用JavaScript获取URL中的参数值
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"> <title>测试JS获取…
LeetCode实战：最长回文子串
题目英文 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer.Example 2: Input: &quo…
2017年9月11日 梁勇 java教材 编程练习题 第二章 2.15 键盘 读取两个点的坐标值（小数），控制台输出两点间距离。...
package com.swift;import java.util.Scanner;public class PToP {public static void main(String[] args) {Scanner scannew Scanner(System.in);System.out.println("请输入第一个点的坐标值x1");Double x1Double.parseDouble(scan.nextLine());System.out.printl…
学习java技术有前途吗
java技术在我国的普及已经是非常广泛的了，很多人都知道，java行业的发展前景是非常好的，但竞争压力也是非常大的，到底学习java技术有前途吗?来看看下面的详细介绍。 学习java技术有前途吗?目前按照各类招聘来看，Java的…
充分理解表达式——《狂人C》习题解答2(第二章习题5)
/* 编程求1357911。 */ #include <stdio.h> #include <stdlib.h>int main( void ) {printf ("1357911") ; printf ("%d\n" , 1 3 5 7 9 11 ) ;system("PAUSE"); return 0;}这个题目的主要目的有两个： 1.掌握写整…
LeetCode实战：整数反转
题目英文 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321Example 2: Input: -123 Output: -321Example 3: Input: 120 Output: 21Note: Assume we are dealing with an environment which could only store integers …
深度洞悉2017企业IT三大关注焦点
本文讲的是深度洞悉2017企业IT三大关注焦点【IT168 云计算】随着经济走向整体放缓，2017有哪些议题会受到企业IT的关注? 一：如何提升员工工作体验 随着80后、90后成为职场主力军，数字化工作场所的推行与建立日渐成为主流，企业将更…
APP测试和传统软件测试有什么区别
APP测试和传统软件测试有什么区别?APP测试和传统测试是有一些区别的，移动APP的特点使得它与传统软件在开发、测试方面都有所不同。比较移动APP测试与传统软件测试的不同，要从以下几个方面进行考虑： (1) 页面布局不同 对于传统软件࿰…
LeetCode实战：字符串转换整数 (atoi)
题目英文 Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or…
[C#] enum 枚举
默认情况下，枚举第一个值是0， 可显式为枚举赋值。 可以定义枚举的基础类型，如enum E : short {}, sizeof(E) 2；默认情况下是int。 枚举的继承链：ValueType->Enum->enum 枚举类型和基础类型之间的转换都是显式的…
制作Windows Mobile程序安装包
使用Visual Studio 2005制作wm上的cab安装包 打开项目，解决方案中添加新项，添加"智能设置CAB项目"；或者在空VS中新建一个"智能设置CAB项目" 添加新项 左侧的Program Files文件夹，没用可以删除 添加项目主输出…
学Java需要下载什么软件?都有什么作用?
学习java并非大家想象中的那么简单，除了书本和老师面授，软件的使用也有很大的作用，接下来小编为大家分享的就是关于“学Java需要下载什么软件?都有什么作用?”的内容，希望能够给正在学习java知识的同学带来帮助。 学Java需要下载…
一种新的攻击方式：使用Outlook 表单进行横向渗透和常驻
本文讲的是一种新的攻击方式：使用Outlook 表单进行横向渗透和常驻，背景最近我们针对CrowdStrike服务进行例行调查，发现了一种攻击方法，其主要用于横向渗透和系统常驻，而且是以前我们没有看到过的。这种攻击利用Microso…
ACM 1740 A New Stone Game http://acm.pku.cn/JudgeOnline/problem?id=1740
题目大意:有N堆石头,每堆石头数目在1到100之间,最多有10堆.两人分别取走石头.取石头的规则是:每次只能从1堆中取,每次取走至少1个.取过后还可以把这堆的石头任意分配到其它堆上(这些堆必须有石头,废话呵呵),当然也可以不分配.问给定这些石头堆的情况,两人轮流取,谁先取完谁胜利…
LeetCode实战：回文数
题目英文 Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: trueExample 2: Input: -121 Output: false Explanation: From left to right, it reads -121. From ri…
安全测试的基本原则有哪些?
软件测试顾名思义就是要进行软件安全方面的测试，对于软件测试人员来说，软件安全是一个广泛而复杂的主题，完全避免软件安全缺陷问题是不切实际的，但通过安全测试可以发现并修复软件大部分安全缺陷。下面介绍一些安全测试的基本原则…
LeetCode实战：盛最多水的容器
题目英文 Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a conta…
微软极品Sysinternals Suite工具包使用指南
微软极品Sysinternals Suite工具包使用指南 按照名称首字母排序，点击每个蓝色标题链接都可以转到微软的对应官方页面，有对这些工具包的直接下载地址和更详尽的用法。因为每个软件几乎都可以长篇大论的介绍，所以，在此就只做简介和罗…
【布局】圣杯布局双飞翼布局
背景 随着前端技术的发展推进，web端的布局方式已基本成熟，那么在网站布局方式中，三列布局最为常用，布局方式也有很多，渐渐的开发者们开始从效率的角度优化自己的代码“如果三排布局能将中间的模块放在dom树前面&#x…
UI设计师面试如何操作才能获得高薪
UI设计师在近几年是非常吃香的，求职招聘网站上对于UI设计师的要求也越来越高，那么在面试的过程中UI设计师面试如何操作才能获得高薪呢?来看看下面的详细解析。 UI设计师面试如何操作才能获得高薪? 1、行为举止得体大方 我们先从仪态体态方面说…
HDU2673-shǎ崽（水题）
如果不能够直接秒杀的题，就不算水题。又应证了那句话，有时候，如果在水题上卡住，那么此题对于你来说，也就不算是水题了额~~ 刚睡醒，迷迷糊糊。 题目的意思很简单，求一个最大的，再求一…
center os7 安装mysql
安装mariadb MariaDB数据库管理系统是MySQL的一个分支，主要由开源社区在维护，采用GPL授权许可。开发这个分支的原因之一是：甲骨文公司收购了MySQL后，有将MySQL闭源的潜在风险，因此社区采用分支的方式来避开这个风险。M…
LeetCode实战：最长公共前缀
题目英文 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”. Example 1: Input: ["flower","flow","flight"] Output: "fl"…
软件测试培训需要学习什么技术
软件测试技术相对于IT行业的其他技术，学习起来是比较简单的，大多数零基础学员想要进入到IT行业都会优先选择软件测试，那么具体软件测试培训需要学习什么技术呢?来看看下面的介绍就知道了。 软件测试培训需要学习什么技术? 每个软件在上线之…
检测晃动的三种方法
http://stackoverflow.com/questions/150446/how-do-i-detect-when-someone-shakes-an-iphone 我的实现（基于Eran Talmor）： 没必要application.applicationSupportsShakeToEdit YES; Set the applicationSupportsShakeToEdit property in th…
android随手记
Linearlayout: gravity：本元素中所有子元素的重力方向 layout_gravity：本元素对于父元素的重力方向 自定义权限:http://www.cnblogs.com/it-tomorrow/p/4115161.html 注意:1 .在被调用时就算是normal权限也需要在加入,不然会permission Deney,在…
LeetCode实战：最接近的三数之和
题目英文 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example: Given ar…