-
2021-04-23 20:45:35
给定两个大小为 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 double findMedianSortedArrays(int arr1[],int arr2[]) {
int[] resultArr = new int[arr1.length + arr2.length];
for(int i=0;i
resultArr[i]=arr1[i];
}
for(int i=0;i
resultArr[arr1.length+i]=arr2[i];
}
Arrays.sort(resultArr);
System.out.println(Arrays.toString(resultArr));
int startLen=0;
int endLen=0;
if(resultArr.length%2==0) {
endLen=resultArr.length/2;
startLen=endLen-1;
System.out.println("偶数组:"+startLen+","+endLen);
return (double)(resultArr[startLen]+resultArr[endLen])/2;
}else {
startLen=resultArr.length/2;
System.out.println("奇数组:"+startLen+","+endLen);
return resultArr[startLen];
}
}
给定两个大小为 m 和 n 的有序数组 nums1和 nums2。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5
更多相关内容 -
找到数组总和的中位数
2021-02-12 19:41:00正确的O(n)解决方案非常复杂,需要大量的文本,代码和技巧来...它基本上是一个聪明的分而治之算法,除其他外,它利用了这样一个事实:在一个排序的n乘n矩阵中,人们可以在 O(n) 找到小于/大于给定的元素数量号码 k...正确的O(n)解决方案非常复杂,需要大量的文本,代码和技巧来解释和证明 . 更确切地说,令人信服地需要3页,这里可以详细查看http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf(在评论中找到 simonzack ) .
它基本上是一个聪明的分而治之算法,除其他外,它利用了这样一个事实:在一个排序的n乘n矩阵中,人们可以在 O(n) 找到小于/大于给定的元素数量号码 k . 它递归地将矩阵分解为较小的子矩阵(通过仅取奇数行和列,产生具有 n/2 列和 n/2 行的子矩阵),结合上述步骤,导致复杂度为 O(n) + O(n/2) + O(n/4)... = O(2*n) = O(n) . 太疯狂了!
我无法解释它比论文更好, which is why I'll explain a simpler, O(n logn) solution instead :) .
O(n * logn)解决方案:
It's an interview! 你无法及时得到那个 O(n) 解决方案 . 嘿,为什么不提供一个解决方案,虽然不是最优的,但表明你可以做得比其他明显的候选人更好?
我将利用上面提到的 O(n) 算法来查找在排序的 n-by-n 矩阵中小于/大于给定数字 k 的数字量 . 请记住,我们不需要实际的矩阵!由OP描述的两个大小为 n 的数组的笛卡尔和,得到一个排序的 n-by-n 矩阵,我们可以通过考虑数组的元素来模拟如下:
a[3] = {1, 5, 9};
b[3] = {4, 6, 8};
//a + b:
{1+4, 1+6, 1+8,
5+4, 5+6, 5+8,
9+4, 9+6, 9+8}
因此,每行包含非递减数字,每列也包含非递减数字 . 现在,假装给你一个号码 k . 我们想在 O(n) 找到这个矩阵中有多少数字小于 k ,有多少数字更大 . 显然,如果两个值都小于 (n²+1)/2 ,那意味着 k 是我们的中位数!
算法非常简单:
int smaller_than_k(int k){
int x = 0, j = n-1;
for(int i = 0; i < n; ++i){
while(j >= 0 && k <= a[i]+b[j]){
--j;
}
x += j+1;
}
return x;
}
这基本上计算了每行符合条件的元素数量 . 由于行和列已按上面所示排序,因此这将提供正确的结果 . 由于 i 和 j 每次最多迭代 n 次,算法为 O(n) [注意 j 不会在 for 循环内重置] . greater_than_k 算法类似 .
现在,我们如何选择 k ?那是 logn 部分 . Binary Search! 正如其他答案/评论中所提到的,中位数必须是此数组中包含的值:
candidates[n] = {a[0]+b[n-1], a[1]+b[n-2],... a[n-1]+b[0]}; .
只需对此数组[也 O(n*logn) ]进行排序,然后对其运行二进制搜索 . 由于数组现在处于非递减顺序,因此可以直截了当地注意到小于每个 candidate[i] 的数字量也是非递减值(单调函数),这使得它适合于二进制搜索 . 其结果 smaller_than_k(k) 返回小于 (n²+1)/2 的最大数 k = candidate[i] 是答案,并且在 log(n) 迭代中获得:
int b_search(){
int lo = 0, hi = n, mid, n2 = (n²+1)/2;
while(hi-lo > 1){
mid = (hi+lo)/2;
if(smaller_than_k(candidate[mid]) < n2)
lo = mid;
else
hi = mid;
}
return candidate[lo]; // the median
}
-
Java语言怎么计算一个数组中所有数字的中位数呢
2019-10-15 15:57:27Java语言怎么计算一个数组中所有数字的中位数呢 要用代码完整写出来给我看看 -
Java数组中的元素删除并实现向前移的代码
2020-09-02 10:31:16主要介绍了Java数组中的元素删除并实现向前移的代码的相关资料,需要的朋友可以参考下 -
JAVA求数组的平均数,众数,中位数
2021-07-03 13:55:48中位数:中位数是指把一组数据从小到大排列,如果这组数据的个数是奇数,那最中间那个就是中位数,如果这组数据的个数为偶数,那就把中间的两个数之和除以2,所得的结果就是中位数。 众数:众数是指一组数据中出现...目录
1、名称解释
平均数:是指一组数据之和,除以这组数的个数,所得的结果就是平均数。
中位数:中位数是指把一组数据从小到大排列,如果这组数据的个数是奇数,那最中间那个就是中位数,如果这组数据的个数为偶数,那就把中间的两个数之和除以2,所得的结果就是中位数。
众数:众数是指一组数据中出现次数最多的那个数,众数可以是0个或多个。
2、实例代码
(1)求平均数
public static double mean(int[] arr) { int sum = 0; for (int i = 0; i < arr.length; i++) { sum += arr[i]; } return (double) sum / arr.length; }
(2)求中位数
public static double median(int[] arr) { // 先排序 Arrays.sort(arr); // 如果是偶数,则为中间两个数的和除以2 if (arr.length % 2 == 0) { return (double) ((arr[arr.length / 2 - 1] + arr[arr.length / 2])) / 2; } // 否则就是中间这个数 return arr[arr.length / 2]; }
(3)求众数
public static List<Integer> mode(int[] arr) { Map<Integer, Integer> map = new HashMap<>(); Set<Map.Entry<Integer, Integer>> set = map.entrySet(); List<Integer> list = new ArrayList<>(); // 结果 List<Integer> res = new ArrayList<>(); // 统计元素出现的次数,存入Map集合 for (int item : arr) { map.put(item, map.getOrDefault(item, 0) + 1); } // 将出现的次数存入List集合 map.forEach((k, v) -> { list.add(v); }); //集合排序 Collections.sort(list); // 得到最大值 int max = list.get(list.size() - 1); // 根据最大值获取众数 for (Map.Entry<Integer, Integer> entry : set) { if (entry.getValue() == max) { res.add(entry.getKey()); } } return res; }
-
java 数组中两个数的和 等于另一个数x
2013-10-25 22:14:29有一个数组,有一个数x,是否存在数组中两个数之和等于x 两种方法实现,时耗对比 方法1: 先sort, head位置=0, tail位置=x的位置 如果 array[head]+ array[tail] > x; tail--; else head++; 方法2: 暴力破解,两... -
Java数组,去掉重复值、增加、删除数组元素的方法
2020-09-01 09:38:41下面小编就为大家带来一篇Java数组,去掉重复值、增加、删除数组元素的方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧 -
(java)分治法求解两个有序数组共2N个数的中位数
2019-05-30 20:34:54(java) 问题描述:设X[ 0 : n - 1]和Y[ 0 : n – 1 ]为两个数组,每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。 利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。 -
Java||求集合数组中的中位数
2019-08-03 22:05:44中位数: 简单解释就是最中间的那个数,如果集合是奇数个,则中位数是按大小排列最中间那个数,如果集合是偶数个,则中位数就是按大小排列最中间那两个数的平均数。 求解: 先判断这个集合是奇数还是偶数,如果是...中位数:
简单解释就是最中间的那个数,如果集合是奇数个,则中位数是按大小排列最中间那个数,如果集合是偶数个,则中位数就是按大小排列最中间那两个数的平均数。
求解:
- 先判断这个集合是奇数还是偶数,如果是奇数那么就是第(n+1)/2个数 ,下标为(n-1)/2
- 如果是偶数 就是第n/2和n/2+1的数的平均值 也就是下标为n/2-1和n/2的平均值
实现代码:
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class 中位数 { private static double median(List<Integer> list) { double s = 0; Collections.sort(list); int size = list.size(); if(size % 2 != 1){ s = (list.get(size/2-1) + list.get(size/2)+0.0)/2;//加0.0是为了计算是将int类型转换为浮点型 }else { s = list.get((size-1)/2); } return s; } public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); list.add(8); System.out.print("中位数为:"); System.out.println(median(list)); } }
输出示例:
-
java使用Hashtable过滤数组中重复值的方法
2020-09-01 19:19:56主要介绍了java使用Hashtable过滤数组中重复值的方法,涉及java数组遍历及过滤的相关技巧,需要的朋友可以参考下 -
java数组中数字出现次数
2018-12-12 09:18:20public static void main(String[] args) { int[] arr = {1,2,3,3,2,1,... //统计个数 //创建HashMap,key为数组中的值,value为值重复出现的次数 Map&lt;Integer,Integer&gt; map = new HashMap... -
找出无序数组中位数的方法
2020-01-13 13:10:48今早上在LintCode上做到了这种类型的题目,题目要求找到无序数组中位数在数组的位置,一开始想到的是利用快排的思想来做,但是由于只有十五分钟的时间,就直接用最普通的方式做了,思路是map记录位置+sort排序,水... -
java 判断一个数组中的数值是否连续相邻的方法
2020-08-27 21:31:44下面小编就为大家分享一篇java 判断一个数组中的数值是否连续相邻的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 -
java 键盘输入一个数,输出数组中指定元素的示例
2020-08-27 03:59:41今天小编就为大家分享一篇java 键盘输入一个数,输出数组中指定元素的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 -
JAVA数组元素不足位数补0的问题
2019-09-09 16:08:46关于数组之中位数不足使用0来补位有以下几种方法 假设数组如下 int []str={1,12,118}; 变成{0001,0012,01118} 1.使用DecimalFormat工具类 int[] a = {1, 20, 327, 1000}; String[] numss = new String[4]; ... -
Java 对象(数组)占多大空间(几个字节) 手把手做实验
2020-12-21 14:57:47本次实验基于jdk8 64位以及以上版本。本机环境为jdk11 先查看一下jvm启动的默认参数,里面有2个参数值对本次实验会造成影响。 命令行: java -XX:+PrintCommandLineFlags -version 查看jvm默认参数 分别是 -XX:+... -
java解法——寻找两个有序数组的中位数
2020-07-06 14:42:02请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 ... -
在Java数组中查找某个值的位置
2021-10-09 20:56:28在C语言数组中查找某个值的位置,很多人会首先想到用循环的方式查找。但是在Java中Array类会很轻松地解决这个。 public static int binarSearch(dounle[] a,double num) 在数组a中查找num,返回num在a的位置 ... -
寻找两个有序数组的中位数(Java)
2019-10-06 11:22:47寻找两个有序数组的中位数 题目: 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。 思想... -
Java 数组的使用
2021-08-14 13:50:26① T,即Type,表示:数组中存放元素的类 ② T[ ], 表示:数组的类型 ③ N, 表示:数组的长度 举例: 创建一个可以容纳10个int类型元素的数组 int[] array1 = new int[10]; 创建一个可以容纳5个doub -
基于java中byte数组与int类型的转换(两种方法)
2020-09-01 19:20:55下面小编就为大家带来一篇基于java中byte数组与int类型的转换(两种方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧 -
Java实现 LeetCode 4 寻找两个有序数组的中位数.pdf
2021-08-09 16:39:56Java实现 LeetCode 4 寻找两个有序数组的中位数.pdf -
java数组
2021-03-06 01:07:34数组的好处:可以自动给数组中的元素从0开始标号,方便操作这些元素。格式1:元素类型[] 数组名= new元素类型[元素个数或数组长度];格式2:元素类型[] 数组名= new元素类型[] {元素,元素,......};int[] arr = new ... -
剑指Offer Java版 面试题56:数组中数字出现的次数
2021-03-10 03:24:52题目一:数组中只出现一次的两个数字。一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。练习地址参考答案我们从头到尾依次... -
java – 在数组中找到最接近的数字
2021-02-28 12:26:38一个主意:int nearest = -1;int bestDistanceFoundYet = Integer.MAX_INTEGER;// We iterate on the array...for (int i = 0; i < array.length; i++) {// if we found the desired number, we return it.if ... -
Java实现 LeetCode 4 寻找两个有序数组的中位数
2020-02-11 18:54:06寻找两个有序数组的中位数 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: ... -
java 数组中两两相加等于某个数的组合种数 蛮力解法 排序解法
2017-05-03 22:45:09求数组中两两相加等于某个数的组合中种数 下面提两种解法: 1.蛮力算法:时间复杂度为O(n^2) 2.排序法: 时间复杂度为O(logn) 对数组先进行排序,定义begin和end分别指向数组的 第一个元素和最后一个元素,分为... -
在java中如何计算数组元素的个数
2022-04-09 18:18:39主题:利用: .length可以计算出数组元素的个数 一维数组的计算: 如上图所示,这样我们就可以计算出一个一维数组元素的个数了 二位数组元素个数计算: -
java 计算中位数方法
2019-01-04 15:51:14最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个 先说说什么是中位数: 中位数就是中间的那个数, 如果一个集合是奇数个,那么中位数就是按大小排列...