两个排序数组的中位数
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;
}
}
