兩個排序數組的中位數
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中文網其他相關文章！
