二分查找

两个排序数组的中值

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中文网其他相关文章！