两个排序数组的中值
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { //merge these two arrays and find the median of the newly sorted array int arr[] = new int[nums1.length + nums2.length]; sort(nums1,nums2,arr); return findMedian(arr); } public double findMedian(int arr[]){ int mid = arr.length/2; if(arr.length %2!=0){ return (double)arr[mid]; } else{ return (double)((double)(arr[mid]+arr[mid-1])/2); } } public void sort(int a[], int b[], int arr[]){ int p = 0; int q = 0; int k =0; while(p<a.length && q < b.length){ if(a[p]<b[q]){ arr[k] = a[p++]; } else{ arr[k] = b[q++]; } k++; } while(p<a.length){ arr[k++] = a[p++]; } while(q<b.length){ arr[k++] = b[q++]; } } }
分配书籍
说明:
给出:
Input: ‘n’ = 4 ‘m’ = 2 ‘arr’ = [12, 34, 67, 90]
我们得到了书籍 arr 的列表,其中 arr[i] 在书中有页面 i
我们也有 m 个学生,我们必须分配书籍,使所有书籍连续分配给 m 个学生(同一本书不会分配给两个学生)
现在这本书可以有很多连续的发行版
假设 arr = [12, 34, 67, 90],并且 m = 2
我们将有两个arr分区
喜欢12|34,67,90>学生 1 将有 12 页,学生 2 将有 191 页
或12,34| 67,90>学生 1 将有 55 页,学生 2 将有 157 页
或
12,34,67|90>学生 1 将有 113 页,学生 2 将有 90 页
在所有分布中,最大最小数量。分配的页面数为 113
直觉:
我们必须选择最小编号。学生可以持有的页数,使得所有学生至少拿到一本书
在给定的示例中,最大页数为 90,这可以是学生必须持有的最小页数(否则任何学生都无法持有第 90 页的书)
现在我们将尝试看看它是否是最大最小值。页数与否
[12, 34, 67, 90],学生 = 2
迭代 1 为 90:
学生 1
12+34<90 正确,但 12+34+67 >90 因此学生 1 将持有 12+34 = 46 页
学生2
67+90> 90 因此学生 2 将容纳 67 页
但是有一本书还剩 90 页要分配,我们需要另一名学生
这会将学生人数增加到 3,这是不可能的
因此最大最小图书数不能为 90
我们将尝试使用迭代 91,92,………MaxMinPage除非我们找到可用于分配所有书籍的最大最小页面致所有 2 位学生,这将是我们的答案
注意:我们不能永远继续下去......我们必须在某些页数正确时停止,因此最大页数将为 sum(arr)
//for more details refer : https://youtu.be/Z0hwjftStI4?t=1412 for binary search ///brute force: //tc: O(sum-max)*n import java.util.*; public class Solution { public static int findPages(ArrayList<Integer> arr, int n, int m) { if(m>n) return -1; // brute force int maximum = Integer.MIN_VALUE; int sum =0; for(int i : arr){ maximum = Integer.max(i,maximum); sum+=i; } for(int max = maximum;max<=sum;max++){ int student = allocate(max,arr); if(student ==m) return max; } return -1; } public static int allocate(int pages, ArrayList<Integer> arr){ int student =0; int currentPagesForStudent =0; for(int i =0;i<arr.size();i++){ if(currentPagesForStudent+arr.get(i)<=pages){ currentPagesForStudent+=arr.get(i); } else{ currentPagesForStudent = arr.get(i); student++; } } return student+1; } } ///binary search://tc : O((log(sum-maximum-1)*(n)), where n is the arr.size() import java.util.*; public class Solution { public static int findPages(ArrayList<Integer> arr, int n, int m) { // book allocation impossible if (m > n) return -1; int low = Collections.max(arr); int high = arr.stream().mapToInt(Integer::intValue).sum(); while (low <= high) { int mid = (low + high) / 2; int students = allocate(mid,arr); if (students > m) { low = mid + 1; } else { high = mid - 1; } } return low; } public static int allocate(int pages, ArrayList<Integer> arr){ int student =0; int currentPagesForStudent =0; for(int i =0;i<arr.size();i++){ if(currentPagesForStudent+arr.get(i)<=pages){ currentPagesForStudent+=arr.get(i); } else{ currentPagesForStudent = arr.get(i); student++; } } return student+1; } }
以上是二分查找的详细内容。更多信息请关注PHP中文网其他相关文章!