有序数组取中值
程序员文章站
2022-07-11 16:59:48
一、有两个有序数组 查找出中位数,并且输出 如:arr1[] = {1, 3, 5, 7, 9, 11, 343, 5645, 56756}; arr2[] = {0, 2, 4, 6, 8, 10}; 输出值为 7.0 1、通过合并取值,时间复杂度O(m+n) 3、递归二分查找法,时间复杂度为O( ......
一、有两个有序数组 查找出中位数,并且输出
如:arr1[] = {1, 3, 5, 7, 9, 11, 343, 5645, 56756}; arr2[] = {0, 2, 4, 6, 8, 10}; 输出值为 7.0
1、通过合并取值,时间复杂度o(m+n)
private static double findmidnumber(int arr1[], int arr2[]) { int len1 = arr1.length; int len2 = arr2.length; int arr3[] = new int[len1 + len2]; int i = 0,j = 0, k = 0; while (i < len1 && j < len2) { if (arr1[i] <= arr2[j]) { arr3[k++] = arr1[i]; i++; } else { arr3[k++] = arr2[j]; j++; } } while (i < len1) { arr3[k++] = arr1[i++]; } while (j < len2) { arr3[k++] = arr2[j++]; } system.out.println("find + " + k); if (arr3.length % 2 == 0) { return (arr3[(len1 + len2) / 2 - 1] + arr3[(len1 + len2) / 2]) / 2.0; } else { return arr3[(len1 + len2) / 2] * 1.0; } }
2、取最大中值,时间o(k)
private static double findmidnumber1(int arr1[], int arr2[]) { int len1 = arr1.length; int len2 = arr2.length; int arr3[] = new int[(len1 + len2) / 2 +1]; int i = 0,j = 0, k = 0, index = 0; while (index < arr3.length && j < len2 && i < len1) { if (arr1[i] <= arr2[j]) { arr3[index++] =arr1[i]; i ++; } else { arr3[index++] =arr2[j]; j++; } k ++; } while (index < arr3.length) { if ( i < len1) { arr3[index++] =arr1[i++]; } if ( j < len2) { arr3[index++] =arr2[j++]; } k ++; } system.out.println("find1 + " + k); if (arr3.length % 2 == 1) { return (arr3[arr3.length - 2] + arr3[arr3.length - 1] )/ 2.0; } else { return arr3[arr3.length - 1] * 1.0; } }
3、递归二分查找法,时间复杂度为o(log(m+n)
private static double findmidnumber3(int arr1[], int arr2[]) { int len1 = arr1.length; int len2 = arr2.length; int l = (len1 + len2 + 1) / 2; int r = (len1 + len2 + 2) / 2; return (findmin(arr1, 0, arr2, 0, l) + findmin(arr1, 0, arr2, 0, r)) / 2.0; } private static int findmin(int arr1[], int l, int arr2[],int r, int k) { if (l > arr1.length - 1) return arr2[r + k -1]; if (r > arr2.length - 1) return arr1[l + k -1]; if (k == 1) return math.min(arr1[l], arr2[r]); n++; int min1 = integer.min_value, min2 = integer.min_value; if (l + k/2 -1 < arr1.length) { min1 = arr1[l + k/2 -1]; } if (r + k/2 -1 < arr2.length) { min2 = arr2[r + k/2 -1]; } return (min1 < min2) ? findmin(arr1, l + k/2, arr2, r, k - k/2) : findmin(arr1, l, arr2, r + k/2, k - k/2); }
上一篇: java基础第十篇之异常
下一篇: HashMap1.8之节点删除分析