二分查找

兩個排序數組的中位數

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中文網其他相關文章！