Recherche binaire

Médiane de deux tableaux triés

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

Attribuer des livres

Explication :

donné :

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

on nous donne la liste des livres arr, où arr[i] a des pages dans le livre i

on nous donne également m étudiants, nous devons attribuer des livres de telle sorte que tous les livres soient répartis de manière contiguë entre m étudiants (le même livre n'est pas attribué à deux étudiants)

maintenant, il peut y avoir beaucoup de distributions contiguës du livre

disons arr = [12, 34, 67, 90], et m = 2

Nous, aurons deux partitions de l'arr

j'aime 12|34,67,90 > l'élève 1 aura 12 pages, l'élève 2 aura 191 pages

ou 12,34| 67,90> l'élève 1 aura 55 pages, l'élève 2 aura 157 pages

ou

12,34,67|90> l'élève 1 aura 113 pages, l'élève 2 aura 90 pages

parmi toute la distribution, maximum minimum no. des pages allouées est 113

Intuition :

Nous devons choisir le minimum non. de pages qu'un élève peut tenir de telle sorte que tous les élèves obtiennent au moins un livre

Dans l'exemple donné, le nombre maximum de pages est 90, cela peut être la page minimale que l'élève devra détenir (sinon le livre avec la page 90 ne peut être détenu par aucun élève)

maintenant nous allons essayer de voir si c'est le maximum minimum non. de pages ou pas

[12, 34, 67, 90], élèves = 2

itération 1 avec 90 :

pour l'élève 1

12+34<90 vrai, mais 12+34+67>90 donc l'élève 1 tiendra 12+34 = 46 pages

pour l'élève 2

67+90> 90 donc l'élève 2 tiendra 67 pages

Mais il reste un livre de 90 pages pour que cela soit alloué, nous aurons besoin d'un autre étudiant

Cela augmentera le nombre d'élèves à 3, ce qui n'est pas possible

Par conséquent, le livre minimum maximum ne peut pas être de 90

Nous allons essayer avec Itération 91,92,………MaxMinPage à moins que nous trouvions la page min max qui peut être utilisée pour attribuer tout le livre à tous les 2 étudiants ce sera notre réponse

remarque : nous ne pouvons pas continuer éternellement…nous devrons nous arrêter à un certain nombre de pages, donc le nombre maximum de pages sera 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;

    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!