Binäre Suche

Median zweier sortierter Arrays

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++];
        }
    }
}

Bücher zuordnen

Erklärung:

gegeben :

Input: ‘n’ = 4 ‘m’ = 2
‘arr’ = [12, 34, 67, 90]

Wir erhalten eine Liste der Bücher arr, wobei arr[i] Seiten im Buch i hat

Wir bekommen auch m Studenten, wir müssen Bücher so zuteilen, dass alle Bücher zusammenhängend auf m Studenten verteilt sind (dasselbe Buch wird nicht zwei Studenten zugewiesen)

Jetzt kann es viele zusammenhängende Verteilungen des Buches geben

sagen wir arr = [12, 34, 67, 90] und m = 2

Wir werden zwei Partitionen des Arr haben

wie 12|34,67,90 > Student 1 wird 12 Seiten haben, Student 2 wird 191 Seiten haben

oder 12,34| 67,90 > Student 1 wird 55 Seiten haben, Student 2 wird 157 Seiten haben

oder

12,34,67|90 > Student 1 wird 113 Seiten haben, Student 2 wird 90 Seiten haben

unter allen Verteilungen maximale minimale Anzahl. der zugewiesenen Seiten beträgt 113

Intuition:

Wir müssen die Mindestanzahl wählen. Anzahl der Seiten, die ein Schüler halten kann, sodass alle Schüler mindestens ein Buch erhalten

Im angegebenen Beispiel beträgt die maximale Seitenanzahl 90. Dies kann die Mindestseite sein, die der Schüler halten muss (sonst kann ein Buch mit Seite 90 von keinem Schüler gehalten werden)

Jetzt werden wir versuchen herauszufinden, ob es sich um die maximale Mindestanzahl handelt. Anzahl der Seiten oder nicht

[12, 34, 67, 90], Studenten = 2

Iteration 1 mit 90:

für Schüler 1

12+34<90 stimmt, aber 12+34+67 >90, daher hat Schüler 1 12+34 = 46 Seiten

für Schüler 2

67+90 > 90, daher hat Student 2 67 Seiten

Aber es gibt noch ein Buch mit 90 Seiten, damit es vergeben werden kann. Wir brauchen einen weiteren Studenten

Dadurch erhöht sich die Schülerzahl auf 3, was nicht möglich ist

Daher darf das maximale Mindestbuch nicht 90 betragen

Wir werden es mit Iteration 91,92 versuchen,………MaxMinPage, es sei denn, wir finden die maximale Mindestseite, die zum Zuweisen des gesamten Buches verwendet werden kann An alle 2 Studenten, das wird unsere Antwort sein

Hinweis: Wir können nicht ewig weitermachen … wir müssen bei einer bestimmten Seitenzahl aufhören, daher beträgt die maximale Seitenzahl 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;

    }
}

Das obige ist der detaillierte Inhalt vonBinäre Suche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!