leetcode 4:两个排序数组的中位数

2024-09-02 15:38

本文主要是介绍leetcode 4:两个排序数组的中位数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

寻找中位数,当m+n是奇数时,中位数为第(m+n+1)/2个数,当m+n为偶数时,中位数为第(m+n+1)/2和(m+n+2)/2的平均数

根据整数的取整,我们可以统一为中位数为第(m+n+1)/2和(m+n+2)/2的平均数。

如何使用二分法求两个有序数组的第k个数

首先将数组A和数组B分为left_A(下标为0~k/2-1),right_A,left_B(下标为0~k/2-1),right_B

如果left[k/2-2]>right[k/2] 第k个值在left_A,right_A,right_B中

反之,第k个值在left_B,right_A,right_B中

int getKth(int* ln, int m, int* rn, int n, int k) {if (m > n) {return getKth(rn, n, ln, m, k);}if (m == 0) {return rn[k - 1];}if (k == 1) {return std::min(ln[0], rn[0]);}int i = std::min(m, k / 2), j = std::min(n, k / 2);if (ln[i - 1] > rn [j - 1]) {return getKth(ln, m, rn + j, n - j, k - j);} else {return getKth(ln + i, m - i, rn, n, k - i);}
}
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int l=(m+n+1)/2;int r=(m+n+2)/2;int *ln=m>0?&nums1[0]:NULL;int *rn=n>0?&nums2[0]:NULL;return (getKth(ln,m,rn,n,l)+getKth(ln,m,rn,n,r))/2.0;
}

 

这篇关于leetcode 4:两个排序数组的中位数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1130369

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In