دو ترتیب شدہ اشاروں کا میڈین  


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل بلومبرگ ByteDance فیس بک گولڈمین سیکس گوگل مائیکروسافٹ چاہتے ہیں
لڑی ثنائی تلاش تقسیم اور فتح

دو ترتیب شدہ اشاروں A اور B کو سائز n اور m بالترتیب دیا گیا۔ ترتیب شدہ فائنل کا میڈین ڈھونڈیں صف دیئے گئے دو صفوں کو ضم کرنے کے بعد یا دوسرے الفاظ میں ، ہم کہتے ہیں کہ دو طرح کی صفوں کا میڈین تلاش کریں۔

(متوقع وقت کی پیچیدگی: O (لاگ (این))

میڈین آف دو سلارڈ اری کے لئے 1 تک رسائی حاصل کریں  

دو نکاتی طریقہ کا استعمال کرتے ہوئے ، A اور B کی مربوط ترتیب شدہ سرنی تشکیل دیں۔

پھر بس اس صف کے وسط کو تلاش کریں۔

سی ++ پروگرام میڈین آف دو سلارڈ اری کے لئے

#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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی: O (زیادہ سے زیادہ (این ، ایم) کیونکہ ہم دونوں صفوں کا استعمال کرکے ملاوٹ شدہ ترتیب کو تلاش کرتے ہیں۔

یہ بھی دیکھتے ہیں
ضرب بدلاؤ اور مصنوع کے لئے صفوں کے سوالات

خلائی پیچیدگی: O (n + m) کیونکہ ہم حتمی ضم شدہ صف کو محفوظ کرتے ہیں جو ہمیں O (n + m) خلائی پیچیدگی کی طرف لے جائے گا۔

میڈین آف دو سلارڈ اری کے لئے 2 تک رسائی حاصل کریں  

اس مسئلے کو حل کرنے کے ل we ، ہمیں پہلے یہ سمجھنے کی ضرورت ہے کہ میڈین دراصل کیا کرتا ہے۔

یہ دو مساوی لمبائیوں میں سیٹ کی تقسیم ہے جس میں ایک سب سیٹ دوسرے سے بڑا ہے۔

یعنی سیٹ کو دو ذیلی سیٹوں میں تقسیم کریں تاکہ ایک سبسیٹ کا ہر عنصر دوسرے سبسیٹ کے ہر عنصر سے بڑا ہو۔

اب اس مسئلے کی طرف واپس آجائیں ، ہمیں دو ترتیب شدہ اشاروں کا میڈین تلاش کرنے کی ضرورت ہے۔

کیا ہم سرنی A اور B کے لئے ایسی پارٹیشن ڈھونڈ سکتے ہیں ، جیسے دونوں حصوں کے بائیں اور دونوں حصوں کے دائیں کا اضافہ کرکے حاصل کردہ سبسیٹس کی لمبائی برابر ہو؟

دو ترتیب شدہ اشاروں کا میڈینپن

 

ith پوزیشن پر کسی سرنی کو تقسیم کرنا بھی اس سرے سے موجود عناصر کی تعداد کو ظاہر کرتا ہے جو بائیں سبسیٹ میں موجود ہیں۔

اور جیسا کہ ہم جانتے ہیں کہ حاصل کردہ سبسیٹس کی لمبائی برابر ہونی چاہئے ، لہذا

پارٹیشن اے + پارٹیشنبی = (لمبائی (اے) + لمبائی (بی) +1) / 2

(اگر حتمی ضم شدہ ترتیب شدہ سرے کی لمبائی عجیب ہے تو ، بائیں سبسیٹ میں مزید عناصر ہوں گے)

اب صرف ایک چیز بچ گئی ہے یہ دیکھنا ہے کہ دیئے گئے دو اراؤں کو کیسے تقسیم کیا جائے کہ دائیں سبسیٹ بائیں سبسیٹ سے زیادہ ہے۔

آئیے ترتیب شدہ صفوں کی کامل تقسیم کی وضاحت کریں:

ہم کہتے ہیں کہ ہمارے پاس صف A (لمبائی ن) اور ایک سرنی B (لمبائی میٹر) ہے

دو ترتیب شدہ اشاروں کا میڈینپن

 

اس کے بعد ہم نے A پر i اور B پر تقسیم کیا ہے

ایک کامل تقسیم اس وقت ہوتی ہے جب:

  • i + j = (n + m + 1) / 2 (سبسٹس برابر لمبائی کے ہیں)
  • A [i-1] <= B [j] (میں بائیں طرف A کے عنصر بائیں سبسیٹ میں آؤں گا)
  • B [j-1] <= A [i] (J کے بائیں طرف B کے عناصر بائیں سبسیٹ میں آئیں گے)
یہ بھی دیکھتے ہیں
دو ارایوں کا چوراہا

اگر A [i-1]> B [j] اس کا مطلب ہے کہ A کی تقسیم کے بائیں طرف کچھ عناصر موجود ہیں جن کو بڑے (دائیں) سبسیٹ میں رکھنا چاہئے۔ اس صورت میں ، ہم i کو بائیں اور j کو دائیں طرف منتقل کریں گے۔

اگر B [j-1]> A [i] اس کا مطلب ہے کہ بی کے تقسیم کے بائیں حصے میں کچھ ایسے عناصر موجود ہیں جن کو بڑے (دائیں) سبسیٹ میں رکھنا چاہئے۔ اس صورت میں ، ہم j کی طرف بائیں طرف جائیں گے اور میں دائیں طرف جاؤں گا۔

اب اپنے پارٹیشن پوائنٹ کو منتقل کرنے کے ل we ہم بائنری سرچ استعمال کرسکتے ہیں۔

وضاحت

آئیے اسے ایک مثال کے ساتھ سمجھیں:

دو ترتیب شدہ اراے A اور B دیئے گئے۔

آئیے بائنری سرچ کا استعمال کرتے ہوئے A کو تقسیم کرنا شروع کریں اور چیک کریں کہ کیا ہمیں کامل تقسیم مل سکتا ہے یا نہیں۔

مرحلہ 1

بائیں = 0

دائیں = 6

وسط = (0 + 6) / 2 = 3 (تقسیم A)

ہم تقسیم A + پارٹیشن بی = (لمبائی (A) + لمبائی (B) +1) / 2 کا استعمال کرتے ہوئے بی کا حص getہ حاصل کرسکتے ہیں۔

پارٹیشن بی = (6 + 4 + 1) / 2 - پارٹیشن اے

پارٹیشنبی = 5-3 = 2

پن

بی کے تقسیم کا حصہ A کے تقسیم کے دائیں سے زیادہ ہے۔ اس کا مطلب ہے کہ کامل تقسیم کے ل we ہمیں A کے مزید عناصر شامل کرنا ہوں گے۔

مرحلہ 2

بائیں = وسط + 1 یعنی بائیں = 4 کریں

دائیں = 6

لہذا نیا وسط = (4 + 6) / 2 = 5

پارٹیشن بی = (6 + 4 + 1) / 2 - پارٹیشن اے

پارٹیشنبی = 0

پن

جیسا کہ A کا بقیہ حصہ B کے تقسیم کے دائیں سے زیادہ ہے۔ اس کا مطلب ہے کہ کامل تقسیم کے ل we ہمیں بی کے مزید عناصر کو شامل کرنا چاہئے۔

مرحلہ 3

صحیح کریں = وسط 1

بائیں = 4۔

حق = 4

لہذا نیا وسط = (4 + 4) / 2 = 4

پارٹیشن بی = (6 + 4 + 1) / 2 - پارٹیشن اے

پارٹیشنبی = 1

پن

اب ہم دیکھ سکتے ہیں کہ منسلک اعداد و شمار میں کل 5 عنصر ہیں اور اس سے باہر کل 5 عنصر ہیں۔

نیز ، اے کی تقسیم کا بائیں حصہ بی کے تقسیم کے دائیں سے بھی کم ہے۔

اور بی کے تقسیم کا بائیں حصہ A کے تقسیم کے دائیں سے کم ہے۔

یہ بھی دیکھتے ہیں
ڈبللی لنکڈ لسٹ کا استعمال کرتے ہوئے Deque کا نفاذ

لہذا ہماری سرنی اس طرح ضم ہوجائے گی:

پن

چونکہ ہماری صف برابر کی ہے لہذا حتمی ترتیب والے سرے کے اوسط دو عنصروں کی اوسط لے کر میڈین حاصل کیا جائے گا:

  • ایک کامل تقسیم کے بائیں جانب کی زیادہ سے زیادہ یعنی زیادہ سے زیادہ (17,11،XNUMX) ہوگا۔
  • دوسرا کامل تقسیم کے دائیں طرف کی کم از کم حد تک ہو گا یعنی منٹ (19,18،XNUMX)۔

ہے نا؟

میڈین حاصل شدہ = (17 + 18) / 2

17.5 =

اگر انضمام شدہ ترتیب شدہ سرے کی لمبائی عجیب ہے ، تو اس کا جواب صرف کامل تقسیم کے بائیں طرف کا زیادہ سے زیادہ ہوگا۔

مثال کے طور پر

ان پٹ:

ان پٹ کی پہلی لائن میں دو عددی این اور ایم شامل ہیں ، جو A اور B کے سائز کو ظاہر کرتے ہیں۔

اگلی لائن میں n جگہ سے الگ الگ عددی اجزا شامل ہیں جو A [i] کو ظاہر کرتا ہے جہاں 0 <= i

اگلی سطر میں میٹر سے الگ الگ عددی اجزا شامل ہیں جو B [i] کو ظاہر کرتے ہیں جہاں 0 <= i

: پیداوار

دیئے گئے دو ترتیب شدہ اشاروں کا میڈین پرنٹ کریں۔

سی ++ پروگرام میڈین آف دو سلارڈ اری کے لئے

#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

دو ترتیب شدہ اریوں کی میڈین کیلئے جاوا پروگرام

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

دو ترتیب شدہ اشاروں کی میڈین کیلئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی: O (لاگ (n))

یہ بھی دیکھتے ہیں
پاسکل مثلث لیٹ کوڈ

جیسا کہ ہر قدم پر ، ہم تلاش کی جگہ کو نصف کے ذریعہ کم کر رہے ہیں (یا تو وسطی اشاریہ سے بائیں طرف کی تلاش کی جگہ یا دائیں تلاش کی جگہ کا انتخاب کریں)۔

خلائی پیچیدگی: O (1) کیونکہ ہم محض حساب کے لئے کچھ متغیرات استعمال کرتے ہیں۔

پڑھنے کا شکریہ!!

حوالہ جات