`
kmplayer
  • 浏览: 509793 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求两个数组的中位数

阅读更多
1,题目
有两个数组,均已经按升序排列好,编程序计算这两个数组的中位数
要求:要求时间复杂度O(lgn)   空间复杂度O(1)
例子:
数组A:{1,4,6,7,9}   B{2,3,5,8}     两数组合并后{1,2,3,4,5,6,7,8,9}   中位数就是中间的那个数: 5
2,方法:

对两个数组分别二分找解
对每个元素可以O(1)判断它在另外一个数组应该所在的位置,从而可以判断选大了还是小了,继续二分直到找到解为止

先二分第一个数组找解,可选区域为[0,4]。选中A[2]=6,6前面有两个元素,如果将其插入第二个数组,那么6如果是解,则必须前面有4-2=2个元素(排第三位)
通过比较前后元素发现6放在B中的第三位明显大了,需要更小的元素,这样就将下一次二分的区域减了一半.

在A和B中重复这个过程,直到找到解为止

3,3,扩展

M个长度为N的排序好的数组 求中位数
目前有两个比较好的算法

算法一
(1)取所有数组的最小值和最大值,求出全体的最大值和最小值min max 然后取m=(min+max)/2
(2)用m在所有数组中搜索 找到比m小的数的个数n1 若n1大于M*N/2 则mid=(min+mid)/2 否则mid=(mid+max)/2
(3)重复上述搜索一共循环log(max-min)次


算法二
(1)取所有数组的中值排序
弃掉这个最大值所在数组的后半部分和最小值所在数组的前半部分 再将这两个只剩一半的数组合并 O(N)
(2)从合并后的数组中找出中值插入到之前的中值排序数组里 o(logN)
(3)重复(1)(2),每次循环可以舍掉一个数组,一共需要循环M次
分享到:
评论

相关推荐

    分治法求两列有序数组的中位数的程序

    (1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O...思路:对于两个已排好序的数组,可以寻找两个数组中的中位数,只需要进行n次的比较,时间复杂度可以为O(n),代码如下

    两个排序数组中位数

    已经两个已经排好序的数组,找出两个数组合起来的中间大的数字

    C++算法:寻找两个有序数组的中位数

    请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] ...

    找出两数组相同的数(VB6.0源代码编写)

    本示例的焦点在于如何找出并显示两个数组中的相同元素及其位置。以下将详细介绍如何实现这一功能,并提供相关的编程知识。 首先,我们要理解数组的基本概念。在VB6.0中,数组是一种数据结构,可以存储多个相同类型...

    寻找两个正序数组的中位数

    定义分割点 i 在 nums1 中,分割点 j 在 nums2 中,使得 i + j 为两个数组的中位数所需的总元素数的一半。 根据分割点的选择,确保 nums1[i - 1] [j] 和 nums2[j - 1] [i] 这两个条件成立。 计算中位数: 如果满足...

    分治法-中位数

    ### 分治法求解两个有序数组的中位数 #### 分治法简介 分治法是一种重要的算法设计思想,其核心在于将一个复杂的问题分解成若干个规模较小但结构相似的子问题,然后递归地解决这些子问题,并将各个子问题的解组合...

    寻找两个正序数组的中位数1

    - **合并与不合并**:一个直观的解法是将两个数组合并后再求中位数,但这会增加时间复杂度,因为需要进行一次排序。 3. **算法设计**: - **二分查找法**:由于数组已排序,可以考虑使用二分查找法来提高效率。...

    leetcode04_寻找两个正序数组的中位数解法.rar

    leetcode04_寻找两个正序数组的中位数解法.rar !!!CSDN的一个特性: 即使我设置成免费下载,被下载的次数多了之后也会变成付C币下载的了,这个很头疼. !!!因此如果没有C币但想要下载的朋友可以在b站视频下留言给我,留下...

    java 求两个数组中重复元素源代码

    在Java编程中,找出两个数组中的重复元素是一个常见的问题,特别是在数据处理和算法设计中...以上就是关于“java求两个数组中重复元素源代码”的详细解析,涵盖了数组操作、重复元素查找、代码实现及优化等方面的知识。

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

    寻找两个正序数组的中位数

    medi:X 和Y 的中位数问题

    设X[0:n-1]和Y[0:n-1]为2 个数组,每个数组中含有n 个已排好序的数。试设计一个O(log n)时间的算法,找出X 和Y 的2n 个数的中位数。 ★数据输入 输入数据第1 行是每个数组中元素个数n;接下来的2 行中每行有n 个整数,...

    python 两个排序数组的中位数

    # 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) # 你可以假设 nums1 和 nums2 不同时为空 # 示例 1: # nums1 = [1, 3] # nums2 = [2] # 中位数是 2.0 # 示例 2: # nums1 = [1, 2] # nums2 ...

    C# 将两个整型数组的元素相加

    为了实现这一功能,我们需要遍历两个数组,并将对应位置的元素相加。这里提供一种常见的实现方法: ```csharp int[] arr1 = {1, 2, 3}; int[] arr2 = {4, 5, 6}; int[] result = new int[arr1.Length]; for (int i...

    c#-Leetcode面试题解之第4题寻找两个正序数组的中位数.zip

    1. **合并与排序**:最直观的方法是将两个数组合并成一个大的正序数组,然后找到中位数。但这种方法的时间复杂度较高,不适用于大数据量的情况。 2. **二分查找法**:更高效的方法是利用二分查找的思想,结合两个...

    c++-c++编程基础之leetcode题解第4题寻找两个正序数组的中位数.zip

    5. 中位数的特殊情况:当两个数组长度不相等时,中位数可能是两个数组的交界点,需要根据长度来确定。 在LeetCode平台上,这个问题通常要求在线求解,所以还需要关注代码的空间复杂度,尽量减少额外空间的使用。 ...

    java面试-leetcode面试java编程题解之第4题寻找两个正序数组的中位数-java题解.zip

    在本题中,由于我们有两个正序数组,所以需要找到这两个数组合并后的中位数。 解决这个问题,我们可以采用以下几种方法: 1. **合并数组法**:将两个数组合并成一个大的正序数组,然后直接找出中位数。这种方法...

    刷题:给两个有序的数组,找出合并后的中位数

    刷题:给两个有序的数组,找出合并后的中位数

    python-leetcode面试题解之寻找两个正序数组的中位数.zip

    首先,我们需要明确问题的要求:给定两个长度为n和m的正序数组nums1和nums2,我们需要找到这两个数组合并后的中位数。中位数是将一组数值从小到大排列后处于中间位置的数,在奇数个数的情况下是中间那个数,偶数个数...

    C语言-C语言编程基础之leetcode题解第4题寻找两个正序数组的中位数.zip

    5. **优化策略**:为了找到两个数组的中位数,不需要将它们完全合并。可以设计一种策略,通过比较两个数组的元素来逐步逼近中位数。 6. **动态规划**:虽然这不是一个典型的动态规划问题,但思考如何用最少的比较...

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

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

Global site tag (gtag.js) - Google Analytics