Carian Binari

Median dua tatasusunan tersusun

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

Peruntukkan buku

Penjelasan:

diberikan :

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

kami diberi senarai buku arr, di mana arr[i] mempunyai halaman dalam buku i

kami diberikan m pelajar juga, kita perlu memperuntukkan buku supaya semua buku diedarkan secara bersambung di kalangan m pelajar (buku yang sama tidak diberikan kepada dua pelajar)

kini terdapat banyak pengedaran buku yang bersebelahan

katakan arr = [12, 34, 67, 90] dan m = 2

Kami, akan mempunyai dua partition arr

seperti 12|34,67,90 > pelajar 1 akan mempunyai 12 muka surat, pelajar 2 akan mempunyai 191 muka surat

atau 12,34| 67,90 > pelajar 1 akan mempunyai 55 muka surat, pelajar 2 akan mempunyai 157 muka surat

atau

12,34,67|90 > pelajar 1 akan mempunyai 113 muka surat, pelajar 2 akan mempunyai 90 muka surat

di antara semua pengedaran, maksimum minimum no. daripada halaman yang diperuntukkan ialah 113

Intuisi:

Kita perlu memilih no minimum. halaman yang boleh dipegang oleh pelajar supaya semua pelajar mendapat sekurang-kurangnya satu buku

Dalam contoh yang diberikan, kiraan halaman maks ialah 90, ini boleh menjadi halaman min yang perlu dipegang oleh pelajar ( jika tidak buku dengan halaman 90 tidak boleh dipegang oleh mana-mana pelajar)

sekarang kita akan cuba lihat sama ada ia adalah no minimum maksimum. halaman atau tidak

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

lelaran 1 dengan 90:

untuk pelajar 1

12+34<90 benar, tetapi 12+34+67 >90 maka pelajar 1 akan memegang 12+34 = 46 muka surat

untuk pelajar 2

67+90 > 90 maka pelajar 2 akan memegang 67 muka surat

Tetapi ada satu buku dengan 90 muka surat yang tinggal untuk ini diperuntukkan kami memerlukan pelajar lain

Ini akan meningkatkan kiraan pelajar kepada 3, yang tidak mungkin

Oleh itu, buku minimum maksimum tidak boleh 90

Kami akan mencuba dengan Lelaran 91,92,………MaxMinPage melainkan kami menemui halaman min maks yang boleh digunakan untuk menetapkan semua buku kepada semua 2 pelajar yang akan menjadi jawapan kami

nota: kita tidak boleh meneruskan selama-lamanya …kita perlu berhenti pada beberapa kiraan halaman dengan betul, jadi kiraan halaman maks ialah jumlah(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;

    }
}

Atas ialah kandungan terperinci Carian Binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!