이진 검색

두 정렬된 배열의 중앙값

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[i]에 책 i의 페이지가 있는 arr 책 목록이 제공됩니다.

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

90을 사용한 반복 1:

학생 1

12+34<90은 사실이지만 12+34+67>90이므로 학생 1은 12+34 = 46페이지를 보유하게 됩니다

학생 2

67+90 > 90이므로 학생 2는 67페이지를 보유하게 됩니다

하지만 할당하려면 90페이지가 남아 있는 책이 한 권 있습니다. 학생이 한 명 더 필요합니다

이렇게 하면 학생 수가 3명으로 늘어나는데 이는 불가능합니다

따라서 최대 최소 도서는 90권이 될 수 없습니다

모든 책을 할당하는 데 사용할 수 있는 최대 최소 페이지를 찾지 않는 한 반복 91,92,………MaxMinPage을 시도해 보겠습니다. 우리의 답이 될 두 학생 모두에게

참고: 영원히 계속할 수는 없습니다. 어느 정도 페이지 수에서 멈춰야 하므로 최대 페이지 수는 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!