二分查找-java教程-PHP中文网

二分查找

王林

发布： 2024-07-24 19:37:38

转载

558人浏览过

二分查找

两个排序数组的中位数

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

直觉:

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

我们必须选择最小的编号。学生可以持有的页数，以便所有学生至少拿到一本书

在给定的示例中，最大页数是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中文网其它相关文章！