java如何计算中位数
就是先排序，然后确定数组长度
根据长度，确定数组下标，就可以
把数据取出来了。2个数据要求平均数
给两个排序好的数组，怎么求两个数组合并后的中位数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package test;
import java.util.Arrays;
import java.util.Comparator;
public class JButtonTest
{
public static void main ( String[] args )
{
int[] arr1 = { 3, 1, 23 };
int[] arr2 = { 27, 7, 2 };
String temp = Arrays.toString (arr1) + Arrays.toString (arr2);
temp = temp.replaceAll (“\\]\\[“, “,”).replaceAll (“\\s”, “”).replaceAll (“[\\[\\]]”, “”);
String[] result = temp.split (“\\,”);
System.out.println (Arrays.toString (result));
Arrays.sort (result, new ComparatorString ()
{
@Override
public int compare ( String o1, String o2 )
{
int a = Integer.parseInt (o1), b = Integer.parseInt (o2);
if (a b)
{
return 1;
}
else if (a b)
{
return -1;
}
else
{
return 0;
}
}
});
System.out.println (Arrays.toString (result));
}
}
找两个有序数组的中位数的几种方式
我用5个思路的来解决两个非减序数组的中位数.但是成功的只有四个,思路3边界问题太严重.
有时间再来弄好他,他在考试中也不适合使用(边界问题没法快速解决,网上也有人说小数据枚举法确定边界),总的来说费事.
主函数:
#include stdio.h
#include time.h
#include limits.h
double findMedianSortedArrays_1(int* nums1, int nums1Size, int* nums2, int nums2Size);
double sss(int a[], int m, int b[], int n, int k);
double findMedianSortedArrays_2(int* nums1, int nums1Size, int* nums2, int nums2Size);
double findMedianSortedArrays_3(int* nums1, int nums1Size, int* nums2, int nums2Size);
double findMedianSortedArrays_4(int* nums1, int nums1Size, int* nums2, int nums2Size);
double findMedianSortedArrays_5(int* nums1, int nums1Size, int* nums2, int nums2Size);
int main() {
clock_t start_t, end_t;
double total_t;
double mid = 0;
// 1 2 3 4 5 6 7 8 9 10 11
int str1[1000] = { 0, 2, 4, 5, 7, 9, 10, 15, 21, 23, 25 }, \
str2[1000] = { 5, 6, 9, 15, 17, 18, 20, 23, 24, 26, 27, 29, 50 };
// 1 2 3 4 5 6 7 8 9 10 11 12 13
start_t = clock();
mid = findMedianSortedArrays_1(str1, 11, str2, 13);
end_t = clock();
total_t = (double)((double)end_t – (double)start_t) / CLOCKS_PER_SEC;
printf(“方法1:CPU 占用的总时间：%f ns\n”, (total_t * 1000000000));
printf(“中位数 %f \r\n”, mid);
start_t = clock();
mid = findMedianSortedArrays_2(str1, 11, str2, 13);
end_t = clock();
total_t = (double)((double)end_t – (double)start_t) / CLOCKS_PER_SEC;
printf(“方法2:CPU 占用的总时间：%f ns\n”, (total_t * 1000000000));
printf(“中位数 %f \r\n”, mid);
start_t = clock();
mid = findMedianSortedArrays_3(str1, 11, str2, 13);
end_t = clock();
total_t = (double)((double)end_t – (double)start_t) / CLOCKS_PER_SEC;
printf(“方法3:CPU 占用的总时间：%f ns\n”, (total_t * 1000000000));
printf(“中位数 %f \r\n”, mid);
start_t = clock();
mid = findMedianSortedArrays_4(str1, 11, str2, 13);
end_t = clock();
total_t = (double)((double)end_t – (double)start_t) / CLOCKS_PER_SEC;
printf(“方法4:CPU 占用的总时间：%f ns\n”, (total_t * 1000000000));
printf(“中位数 %f \r\n”, mid);
start_t = clock();
mid = findMedianSortedArrays_5(str1, 11, str2, 13);
end_t = clock();
total_t = (double)((double)end_t – (double)start_t) / CLOCKS_PER_SEC;
printf(“方法5:CPU 占用的总时间：%f ns\n”, (total_t * 1000000000));
printf(“中位数 %f \r\n”, mid);
return 0;
}
思路一:
/*
方法1:采用归并两个非减数组形成新非减数组,然后求取新数组的中位数.
性能分析:归并两数组的时间复杂度O(n+m),查找中位数时间复杂度O(1).所以时间复杂度O((n+m)*1)=O(m+n)
*/
double findMedianSortedArrays_1(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int i = 0, j = 0, k = 0;
int c[10000] = { 0 };
double mid_f = (nums1Size + nums2Size);
int sign = (!((int)mid_f 0x1));
if ((!nums1Size) (!nums2Size))return -1;
/* mid_f = (mid_f / 2);
if (nums1Size == 0) {
return ((nums2[(int)mid_f] + nums2[(int)(mid_f – sign)]) / 2);
}
if (nums2Size == 0) {
return ((nums1[(int)mid_f] + nums1[(int)(mid_f – sign)]) / 2);
} */
while ((i nums1Size) (j nums2Size))
{
c[k++] = (nums1[i] = nums2[j]) ? nums1[i++] : nums2[j++];
}
while (i nums1Size)
{
c[k++] = nums1[i++];
}
while (j nums2Size)
{
c[k++] = nums2[j++];
}
// mid_f = (k 0x1)? (c[(k / 2)]):(((c[(k / 2 + sign)]) + (c[(k / 2)])) / 2);
mid_f = (((c[(k / 2 – sign)]) + (c[(k / 2)])) / 2);
printf(“OK k = %d (nums1Size + nums2Size) = %d i = %d j = %d \r\n”, k, (nums1Size + nums2Size), i, j);
i = 0;
while(i = k)
{
printf(“c[%d] = %d \r\n”, i, c[i]);
i++;
}
return mid_f;
}
思路二:
double findMedianSortedArrays_2(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int length_c = (nums1Size + nums2Size);
if (length_c == 0)return 0;
if (length_c 0x1)
{
return sss(nums1, nums1Size, nums2, nums2Size, ((length_c / 2) + 1));
}
else
{
return (((sss(nums1, nums1Size, nums2, nums2Size, (length_c / 2))) + (sss(nums1, nums1Size, nums2, nums2Size, ((length_c / 2) + 1)))) / 2);
}
}
double sss(int a[], int m, int b[], int n, int k)
{
//always assume that m is equal or smaller than n
if (m n)
return sss(b, n, a, m, k);
if (m == 0)
return b[k – 1];
if (k == 1)
//return min(a[0], b[0]);
return (a[0] b[0]) ? a[0] : b[0];
//divide k into two parts
// int pa = min(k / 2, m), pb = k – pa;
int pa = ((k / 2) m) ? (k / 2) : m, pb = k – pa;
if (a[pa – 1] b[pb – 1])
return sss(a + pa, m – pa, b, n, k – pa);
else if (a[pa – 1] b[pb – 1])
return sss(a, m, b + pb, n – pb, k – pb);
else
return a[pa – 1];
}
方法三:
double findMedianSortedArrays_3(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int mid1 = (nums1Size / 2), mid2 = (nums2Size / 2); /* even number slect little one,other slect midle one. */
mid1 = (nums1Size == 2) ? (0) : (mid1);
/*nums1Size或nums2Size等于2时,mid 的取值为1,违反了数组长为偶数时,选择中位数下标较小的那个一作为中位数,这一原则.*/
mid2 = (nums2Size == 2) ? (0) : (mid2);
if ((nums1Size == 1) (nums2Size == 1))
{
return ((nums1[0] + nums2[0]) / 2);
}
else if (nums1Size == 1)
{
if (((nums2Size % 2) == 0))
{
if (nums1[0] = nums2[mid2])
{
return (nums2[mid2]);
}
else
{
if (nums1[0] nums2[mid2 + 1])
{
return (nums2[(mid2 + 1)]);
}
else
{
return (nums1[0]);
}
}
}
//这里要考虑nums2[(mid2 – k)]和nums2[(mid2 + k)] (k=1,2,…length(nums2)/2)同nums2[mid2]是否相等的情况!!这样才能保证边界清晰.
else
{
if (nums1[0] = nums2[(mid2 – 1)])
{
return ((nums2[(mid2 – 1)] + (nums2[mid2])) / 2);
}
else if (nums1[0] = nums2[(mid2 + 1)])
{
return ((nums2[mid2]) + (nums2[(mid2 + 1)]) / 2);
}
else/*nums2[(mid2 – k)]nums2[0]、nums1[mid2]nums2[(mid2 + k)]*/
{
return ((nums2[mid2] + nums1[0]) / 2);
}
}
}
else if (nums2Size == 1)
{/*这里有问题,边界不对.*/
printf(“### nums1Size = %d nums1[%d] = %d nums2Size = %d nums2[%d] = %d \r\n”, nums1Size, mid1, nums1[mid1], nums2Size, mid2, nums2[mid2]);
if (((nums1Size % 2) == 0))
{
if (nums2[0] = nums1[mid1])
{
return (nums1[mid1]);
}
else
{
if (nums2[0] nums1[mid1 + 1])
{
return (nums1[(mid1 + 1)]);
}
else
{
return (nums2[0]);
}
}
}
//这里要考虑nums1[(mid1 – k)]和nums1[(mid1 + k)] (k=1,2,…length(nums1)/2)同nums1[mid1]是否相等的情况!!这样才能保证边界清晰.
else
{
if (nums2[0] = nums1[(mid1 – 1)])
{
return ((nums1[(mid1 – 1)] + (nums1[mid1])) / 2);
}
else if (nums2[0] = nums1[(mid1 + 1)])
{
return ((nums1[mid1]) + (nums1[(mid1 + 1)]) / 2);
}
else/*nums1[(mid1 – k)]nums2[0]、nums1[mid1]nums1[(mid1 + k)]*/
{
return ((nums1[mid1] + nums2[0]) / 2);
}
}
}
if (nums1[mid1] == nums2[mid2])
{
return nums1[mid1];
}
else if (nums1[mid1] nums2[mid2])/* [mid1…n] [0…mid2] */
{
return findMedianSortedArrays_3(nums1[mid1], (nums1Size – mid1), nums2[0], (mid2 + 1));
}
else/* [0…mid1] [mid2…m] */
{
return findMedianSortedArrays_3(nums1[0], (mid1 + 1), nums2[mid2], (nums2Size – mid2));
}
return 0;
}
方法四:
/*
从某种程度上来说这是每数组的中位数对比法的一种更完善的思想.通过对比每数组的割处,a[li]b[(a.length+b.length+1-li)+1]和b[a.length+b.length+1-li]a[li+1]同时成立作为退出条件,其他区间为循环和二分法依据.采用manacher算法的技巧实现奇偶性的统一化处理.
性能分析:通过上述的循环查找缩小a数组一半的元素个数,但是最坏要经过m+n次循环.时间复杂度O(log(n+m))
*/
/////////////////////////////////*************4********************//////////////////////////////////
double findMedianSortedArrays_4(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int length_c = (nums1Size + nums2Size);
int len_a = nums1Size, len_b = nums2Size;
int la = 0, lb = 0, ra = 0, rb = 0;
int ca = 0, cb = 0;
int low = 0, high = (2 * len_a);
if ((nums1Size == 0) (nums2Size == 0))return -1;
if (nums1Size == 0) {
return ((nums2[nums2Size / 2] + nums2[nums2Size / 2 – 1]) / 2);
}
if (nums2Size == 0) {
return ((nums1[nums1Size / 2] + nums1[nums1Size / 2 – 1]) / 2);
}
if (nums1Size nums2Size)
{
return findMedianSortedArrays_4(nums2, nums2Size, nums1, nums1Size);
}
while (low = high)
{
ca = ((low + high) / 2);
cb = len_a + len_b – ca;
la = (ca == 0) ? (INT_MIN) : (nums1[((ca – 1) / 2)]);
ra = (ca == (2 * len_a)) ? (INT_MAX) : (nums1[(ca / 2)]);
lb = (cb == 0) ? (INT_MIN) : (nums2[((cb – 1) / 2)]);
rb = (cb == (2 * len_b)) ? (INT_MAX) : (nums2[(cb / 2)]);
printf(“la = %dra = %dlb = %drb = %d \r\n”, la, ra, lb, rb);
if (la rb) {
high = ca – 1;/*二分法的上限移动到中点少1的位置处,抛弃后半部分一半多1个元素.*/
}
else if (lb ra) {
low = ca + 1;/*二分法的下限移动到中点多1的位置处,抛弃前半部分一半多1个元素.*/
}
else {/*else if(la = rb lb = ra)*/
break;
}
}
return ((((la = lb) ? (la) : (lb)) + ((ra = rb) ? (ra) : (rb))) / 2);
}
LeetCode-;两有序数组找中位数答案
方法五:
/*
用统计方法,从小到大对两数组同时进行归并式的遍历,并计数.当计数值等于两数组的中位数的下标,就找到中位数.
性能分析:时间复杂度是归并时间复杂度的一半,即O(m+n)=O((m+n)/2)
*/
double findMedianSortedArrays_5(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int i = 0, j = 0, k = 0;
int middle = (nums1Size + nums2Size);
double sign = (!(middle 0x1));
if ((nums1Size == 0) (nums2Size == 0))return -1;
middle = (middle / 2);
if (nums1Size == 0) {
return ((nums2[(int)middle] + nums2[(int)(middle – sign)]) / 2);
}
if (nums2Size == 0) {
return ((nums1[(int)middle] + nums1[(int)(middle – sign)]) / 2);
}
if (sign) {
for (i = 0, j = 0, k = 0; i = (int)(middle – sign); i++)
{
(nums1[j] = nums2[k]) ? (nums1[(j++)]) : (nums2[k++]);
}
middle = (nums1[j] = nums2[k]) ? (nums1[j–]) : (nums2[k–]);//偶数中位数的前半部分最大值
middle = ((middle + ((nums1[j] = nums2[k]) ? (nums1[j]) : (nums2[k]))) / 2);//[偶数中位数的后半部分最小值 + middle(偶数中位数的前半部分最大值)] / 2 = middle
}
else
{
for (i = 0, j = 0, k = 0; i = (middle – sign); i++)
{
(nums1[j] = nums2[k]) ? (nums1[(j++)]) : (nums2[k++]);
}
middle = (nums1[j] = nums2[k]) ? (nums1[j]) : (nums2[k]);
}
return middle;
}
测试结果:(出现的特例:这着实具有不可避免性.输入全体样本中重复率高时,结束条件能被错误触发.)
/*
OK k = 24 (nums1Size + nums2Size) = 24 i = 11 j = 13
c[0] = 0
c[1] = 2
c[2] = 4
c[3] = 5
c[4] = 5
c[5] = 6
c[6] = 7
c[7] = 9
c[8] = 9
c[9] = 10
c[10] = 15
c[11] = 15
c[12] = 17
c[13] = 18
c[14] = 20
c[15] = 21
c[16] = 23
c[17] = 23
c[18] = 24
c[19] = 25
c[20] = 26
c[21] = 27
c[22] = 29
c[23] = 50
c[24] = 0
方法1:CPU 占用的总时间：4000000.000000 ns
中位数 16.000000
方法2:CPU 占用的总时间：0.000000 ns
中位数 16.000000
nums1Size = 11 nums1[5] = 9 nums2Size = 13 nums2[6] = 20
nums1Size = 6 nums1[3] = 21 nums2Size = 7 nums2[3] = 15
nums1Size = 4 nums1[2] = 15 nums2Size = 4 nums2[2] = 18
nums1Size = 2 nums1[0] = 15 nums2Size = 3 nums2[1] = 17
nums1Size = 2 nums1[0] = 15 nums2Size = 2 nums2[0] = 15
方法3:CPU 占用的总时间：15000000.000000 ns
中位数 15.000000
la = 9 ra = 9 lb = 20 rb = 20
la = 21 ra = 21 lb = 15 rb = 15
la = 10 ra = 15 lb = 17 rb = 18
la = 15 ra = 15 lb = 17 rb = 17
la = 15 ra = 21 lb = 15 rb = 17
方法4:CPU 占用的总时间：10000000.000000 ns
中位数 16.000000
方法5:CPU 占用的总时间：0.000000 ns
中位数 16.000000
*/
两个有序数组的中位数
有两个大小为 n 和 m 的排序数组 nums1 和 nums2 。
请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。
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)).
最简单直接的办法就是合并数组，再取中位数。但是时间复杂度为O(m+n) O(log (m+n))，不符合要求。
略加思索，中位数与位置相关。在一个总长m + n的数组里分割数组的index为(m+n-1)/2。
两个数组内小于等于中位数的数的个数必定等于两个数组内大于等于中位数的数的个数。根据这一特性，我们只要在两个数组里找到两个index，使得 [0, index1) + [0, index2）= （index1, n] + (index2, m] ，便可根据index算出中位数。
由以上推论不难得出：
所有满足以上条件的index1和index2，都能使得两个分割的数组左边和右边数的个数和相等。但并不能保证index1， index2附近就能取到中位数。
若index1，index2 为整数，则nums1[index1], nums2[index2]所取之数就是两个数组的“分割数”，如果两个分割数相同，则该分割数一定为中位数。
若index1，index2 不为整数，则与index邻近的两个整数能取出两个数，即：
那如何根据这4个数判断出中位数呢？看到这里有人可能已经明白了。没明白也没关系，我们来举个栗子。
我们让index1在[ -0.5, 2.5 ]以0.5为步长遍历，初次结果：
最后一次结果（正确结果）：
对比两次结果，不难发现以合法结果中[l1, r1] [l2, r2]是有交集的，即[max(l1,l2), min(r1, r2)]是有效的。
同时如果n+m为奇数，中位数max(l1,l2) = min(r1, r2)；
如果n+m为偶数，中位数为(max(l1,l2) + min(r1, r2))/2。
此时算法的循环次数为((m+n-1)/2 – (m-n-1)/2)*2 = 2m, 时间复杂度为O(2m)，离题目的复杂度还有差距。
我们再把逐步循环替换成二分查找，就可以把复杂度降为O(log(2m)) O(log(n+m))。
java 如何求多个数的中位数 具体！！！
package com.test;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
System.out.println(zhongweishu(7, 4, 8));
}
// 可换为多个数，如参数为：int a,int b,int c,int d,int e
public static int zhongweishu(int a, int b, int c){
int[] nums = {a,b,c};
Arrays.sort(nums); // 数组从小到大排序
return nums[nums.length/2]; // 找出排序后中间的数组值
}
}
微信扫一扫 
支付宝扫一扫 
