İki Sortlaşdırılmış Dizinin Medianı

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Facebook Goldman Sachs google microsoft Arzu
Geyim İkili axtarış Bölün və fəth edinBaxılıb 80

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Müvafiq olaraq n və m ölçülü iki A və B sıra verilmişdir. Sıralanmış finalın medianını tapın array verilmiş iki massivin birləşdirilməsindən sonra əldə edilən və ya başqa sözlə, iki sıralanmış massivin medianını tapdığını söyləyirik.

(Gözlənilən vaxt mürəkkəbliyi: O (log (n)))

İki Sortlanmış Array Median üçün yanaşma 1

İki göstərici metodundan istifadə edərək A və B-nin birləşdirilmiş sıralanmış bir sıra yaradın.

Sonra sadəcə həmin massivin orta hissəsini tapın.

İki Sıralı Dizinin Medianı üçün C ++ Proqramı

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int k=n+m;                   // size of merged sorted array
    int M[k];                   // array which will store integers of A and B in ascending order
    int i=0,j=0,in=0;          // i is a pointer index for A
                              // j is a pointer index for B 
                             // in is a pointer index for M
    while(i<n || j<m){
        if(i<n && j<m){
            if(A[i]<B[j]){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        else{
            if(i<n){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        in++;
    }
    if(k%2==0){
        double m1 = M[k/2];
        double m2 = M[(k/2)-1];
        return (m1+m2)/2;
    }
    else{
        double m1 = M[k/2];
        return m1;
    }
    return -1;    
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
5 5
6 1 2 7 8
3 4 5 6 7
3.5

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi: O (max (n, m), çünki hər iki massivdən də istifadə edərək birləşən sıralanmış massivi tapırıq.

Kosmik Mürəkkəblik: O (n + m), çünki bizi O (n + m) məkan mürəkkəbliyinə aparacaq son birləşdirilmiş massivi saxlayırıq.

İki Sortlanmış Array Median üçün yanaşma 2

Bu problemi həll etmək üçün əvvəlcə medianın həqiqətən nə etdiyini anlamalıyıq.

Çoxluğun iki alt uzunluğa bölünməsidir ki, bir alt digərindən daha böyük olsun.

yəni dəsti iki alt qrupa bölün ki, bir alt çoxluğun hər elementi digər alt elementin hər elementindən böyük olsun.

İndi problemə qayıdın, iki sıralanmış massivin orta ölçüsünü tapmaq lazımdır.

Hər iki bölmənin soluna və hər iki bölmənin sağına əlavə etməklə alınan alt dəstlərin uzunluğu bərabər olan A və B massivi üçün bir bölmə tapa bilərikmi?

İki Sortlaşdırılmış Dizinin MedianıPin

 

Bir massivin ith mövqeyində bölünməsi, eyni zamanda həmin altdakı alt dəstdə olan elementlərin sayını göstərir.

Bildiyimiz kimi əldə edilən alt dəstlərin uzunluğu bərabər olmalıdır

bölmə A + bölmə B = (uzunluq (A) + uzunluq (B) +1) / 2

(Son birləşdirilmiş sıralanmış massivin uzunluğu tək olarsa, sol alt çox elementə sahib olardı)

İndi qalan yeganə şey, verilmiş iki massivin sağ alt çoxluq sol altdan daha böyük olduğu kimi necə bölünəcəyini yoxlamaqdır.

Sıralanmış massivlərin mükəmməl bölməsini təyin edək:

Deyək ki, A (uzunluq n) və B (uzunluq m) bir sıra var.

İki Sortlaşdırılmış Dizinin MedianıPin

 

A-nı i-yə, B-ni j-ə böldük, sonra

Mükəmməl bir bölmə aşağıdakılardır:

  • i + j = (n + m + 1) / 2 (alt dəstlər bərabər uzunluqdadır)
  • A [i-1] <= B [j] (i-nin solundakı A elementləri sol alt hissəyə daxil olacaq)
  • B [j-1] <= A [i] (j-nin solundakı B elementləri sol alt hissəyə daxil olacaq)

Əgər A [i-1]> B [j] deməkdir ki, A hissəsinin solunda daha böyük (sağ) alt hissəyə yerləşdirilməli bəzi elementlər var. Bu vəziyyətdə i-ni sola, j-ni sağa doğru hərəkət etdirəcəyik.

B [j-1]> A [i] deməkdir ki, B hissəsinin solunda daha böyük (sağ) alt hissəyə yerləşdirilməli bəzi elementlər var. Bu vəziyyətdə j-ni sola, i-ni sağa doğru hərəkət etdirəcəyik.

İndi bölmə göstəricilərimizi hərəkət etdirmək üçün ikili axtarışdan istifadə edə bilərik.

Izahat

Bir nümunə ilə başa düşək:

İki sıralanmış A və B massivi verilir.

İkili axtarışdan istifadə edərək A bölməsinə başlayaq və mükəmməl bir bölmə əldə edə biləcəyimizi yoxlayaq.

Step 1

sol = 0

sağ = 6

orta = (0 + 6) / 2 = 3 (A üçün bölmə)

B bölümünü bölmə A + bölmə B = (uzunluq (A) + uzunluq (B) +1) / 2 istifadə edərək əldə edə bilərik

bölüm B = (6 + 4 + 1) / 2 - bölmə A

bölmə B = 5-3 = 2

Pin

B hissəsinin sol hissəsi A hissəsinin sağ hissəsindən daha böyükdür. Bu o deməkdir ki, mükəmməl bölmə üçün daha çox A elementi əlavə etməliyik.

Step 2

Sol = orta + 1, sol = 4 et

sağ = 6

bu səbəbdən yeni orta = (4 + 6) / 2 = 5

bölüm B = (6 + 4 + 1) / 2 - bölmə A

bölmə B = 0

Pin

A hissəsinin sol hissəsi B hissəsinin sağından daha böyük olduğu üçün. Bu o deməkdir ki, mükəmməl bölmə əldə etmək üçün daha çox B elementi əlavə etməliyik.

Step 3

Doğru et = 1-in ortası

Sol = 4

sağ = 4

bu səbəbdən yeni orta = (4 + 4) / 2 = 4

bölüm B = (6 + 4 + 1) / 2 - bölmə A

bölmə B = 1

Pin

İndi əlavə şəkildə cəmi 5 element və xaricində cəmi 5 element olduğunu görə bilərik.

Ayrıca, A hissəsinin sol hissəsi B hissəsinin sağından azdır.

Və B hissəsinin sol hissəsi A hissəsinin sağından azdır.

Beləliklə, serialımız belə birləşəcək:

Pin

Dizimiz bərabər ölçüdə olduğundan, ortalama son sıralanmış massivin orta iki elementinin ortalaması alınaraq əldə ediləcəkdir:

  • Biri, mükəmməl bölmənin sol tərəfinin maksimumu olacaq, yəni max (17,11).
  • İkincisi, mükəmməl bölmənin sağ tərəfinin minimumu olacaq, yəni min (19,18).

Deyilmi?

Əldə olunan orta = (17 + 18) / 2

= 17.5

Birləşdirilmiş sıralanmış massivin uzunluğu tək olarsa, cavab sadəcə mükəmməl bölmənin sol tərəfinin maksimumu olacaqdır.

misal

Input:

Girişin ilk sətri A və B massivinin ölçüsünü göstərən iki n və m tam ədədi ehtiva edir.

Növbəti sətirdə boşluqla ayrılmış n tam ədədi var, burada A <i] göstərilir, burada 0 <= i

Növbəti sətirdə boşluqla ayrılmış m tam ədədi var B [i], burada 0 <= i

Çıxış:

Verilən iki sıralanmış massivin medianını çap edin.

İki Sıralı Dizinin Medianı üçün C ++ Proqramı

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int left = 0, right = n;
    while (left <= right) {
        int partitionA = (left + right)/2;
        int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2

        //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
        double maxLeftA = INT_MIN;
        if(partitionA > 0){
            maxLeftA = A[partitionA-1];
        }
            
        //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
        double minRightA = INT_MAX;
        if(partitionA < n){
            minRightA = A[partitionA];
        }
        
        //Similarly for maxLeftB and minrightB
        double maxLeftB = INT_MIN;
        if(partitionB > 0){
            maxLeftB = B[partitionB-1];
        }
            
        double minRightB = INT_MAX;
        if(partitionB < m){
            minRightB = B[partitionB];
        }
        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
            if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB))/2;
            } 
            else {
                return max(maxLeftA, maxLeftB);
            }
        } 
        else if (maxLeftA > minRightB) {                          //move left side.
            right = partitionA - 1;
        }
        else {                                                   // move right side
            left = partitionA + 1;
        }
    }
    return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
4 5
1 2 7 8
3 4 5 6 7
5

İki Sortlaşdırılmış Array Median üçün JAVA Proqramı

import java.util.Scanner;
public class Main{
    public static double findMedian(int A[], int B[],int n,int m) {
        int left = 0, right = n;
        while (left <= right) {
            int partitionA = (left + right)/2;
            int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2
            //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
            double maxLeftA = Integer.MIN_VALUE;
            if(partitionA > 0){
                maxLeftA = A[partitionA-1];
            }
                
            //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
            double minRightA = Integer.MAX_VALUE;
            if(partitionA < n){
                minRightA = A[partitionA];
            }
                
            //Similarly for maxLeftB and minrightB
            double maxLeftB = Integer.MIN_VALUE;
            if(partitionB > 0){
                maxLeftB = B[partitionB-1];
            }
                    
            double minRightB = Integer.MAX_VALUE;
            if(partitionB < m){
                minRightB = B[partitionB];
            }
            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
                if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                    return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2;
                } 
                else {
                    return Math.max(maxLeftA, maxLeftB);
                }
            } 
            else if (maxLeftA > minRightB) {                          //move left side.
                right = partitionA - 1;
            }
            else {                                                   // move right side
                left = partitionA + 1;
            }
        }
        return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
    }
        
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n,m;
        n = scan.nextInt();
        m = scan.nextInt();
        int A[]=new int[n];
        int B[]=new int[m];
        for(int i=0;i<n;i++){
            A[i] = scan.nextInt();
        }
        for(int i=0;i<m;i++){
            B[i] = scan.nextInt();
        }
        double median = findMedian(A,B,n,m);
        System.out.println(median);  
    }
}
4 6
6 7 8 9
1 2 3 4 5 6
5.5

İki Sortlanmış Array Medianının Mürəkkəblik Analizi

Zaman Mürəkkəbliyi: O (log (n))

hər addımda olduğu kimi, axtarış sahəsini yarıbayarı azaldırıq (ya sol göstərici, ya da orta indeksdən sağ axtarış sahəsi seçirik).

Kosmik Mürəkkəblik: O (1) çünki hesablama üçün yalnız bəzi dəyişənlərdən istifadə edirik.

Oxuduğunuz üçün təşəkkür edirəm !!

References

Crack Sistemi Dizayn Müsahibələri
Translate »