二分探索

ソートされた 2 つの配列の中央値

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 人の生徒に連続して配布されるように本を割り当てなければなりません (同じ本が 2 人の生徒に割り当てられることはありません)

書籍を多数の連続配布できるようになりました

arr = [12, 34, 67, 90]、m = 2 としましょう

ARR は 2 つのパーティションに分けられます

いいね 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

直感:

最小数を選択する必要があります。すべての生徒が少なくとも 1 冊の本を手にできるように、生徒が保持できるページ数

指定された例では、最大ページ数は 90 で、これが生徒が保持する必要がある最小ページになります (そうでない場合、90 ページの本はどの生徒も保持できません)

今度は、それが最大最小番号であるかどうかを確認してみます。ページ数かどうか

[12, 34, 67, 90]、生徒 = 2

90 の反復 1:

生徒 1 用

12+34<90 は true ですが、12+34+67 >90 であるため、生徒 1 は 12+34 = 46 ページを保持することになります

生徒 2 用

67+90> 90 なので、生徒 2 は 67 ページになります

しかし、90 ページが残っている本が 1 冊あり、これを割り当てるには別の生徒が必要です

これにより生徒数は 3 人に増えますが、これは不可能です

したがって、最大最小ブックを 90 にすることはできません

すべての書籍を割り当てるために使用できる最大最小ページが見つからない限り、Iteration 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 中国語 Web サイトの他の関連記事を参照してください。