இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் சராசரி  


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் ByteDance பேஸ்புக் கோல்ட்மேன் சாக்ஸ் கூகிள் மைக்ரோசாப்ட் விஷ்
அணி பைனரி தேடல் பிரித்து வெல்லுங்கள்

முறையே n மற்றும் m அளவு A மற்றும் B ஆகிய இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகள் கொடுக்கப்பட்டுள்ளன. இறுதி வரிசைப்படுத்தப்பட்ட சராசரி கண்டுபிடிக்கவும் வரிசை கொடுக்கப்பட்ட இரண்டு வரிசைகளை ஒன்றிணைத்த பிறகு அல்லது வேறுவிதமாகக் கூறினால், இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் சராசரியைக் கண்டுபிடிப்போம் என்று கூறுகிறோம்.

(எதிர்பார்க்கப்படும் நேர சிக்கலானது: ஓ (பதிவு (என்)))

இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் இடைநிலைக்கு 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது: ஓ (அதிகபட்சம் (n, m) ஏனெனில் இரண்டு வரிசைகளையும் பயன்படுத்தி ஒன்றிணைந்த வரிசைப்படுத்தப்பட்ட வரிசையை நாங்கள் காண்கிறோம்.

மேலும் காண்க
பெருக்கல் மற்றும் தயாரிப்புக்கான வரிசை வினவல்கள்

விண்வெளி சிக்கலானது: O (n + m) ஏனெனில் இறுதியாக ஒன்றிணைக்கப்பட்ட வரிசையை நாங்கள் சேமித்து வைக்கிறோம், இது O (n + m) விண்வெளி சிக்கலுக்கு இட்டுச் செல்லும்.

இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் இடைநிலைக்கு 2 ஐ அணுகவும்  

இந்த சிக்கலை தீர்க்க, சராசரி உண்மையில் என்ன செய்கிறது என்பதை நாம் முதலில் புரிந்து கொள்ள வேண்டும்.

இது இரண்டு சம நீள துணைக்குழுக்களாக தொகுப்பின் பகிர்வு ஆகும், அதாவது ஒரு துணைக்குழு மற்றொன்றை விட அதிகமாக இருக்கும்.

அதாவது, தொகுப்பை இரண்டு துணைக்குழுக்களாகப் பிரிக்கவும், அதாவது ஒரு துணைக்குழுவின் ஒவ்வொரு உறுப்பு மற்ற துணைக்குழுவின் ஒவ்வொரு உறுப்புகளையும் விட அதிகமாக இருக்கும்.

இப்போது மீண்டும் சிக்கலுக்கு வாருங்கள், இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் சராசரியைக் கண்டுபிடிக்க வேண்டும்.

A மற்றும் B வரிசைக்கு ஒரு பகிர்வைக் கண்டுபிடிக்க முடியுமா, அதாவது இரு பகிர்வுகளின் இடது மற்றும் இரு பகிர்வுகளின் வலதுபுறத்தையும் சேர்ப்பதன் மூலம் பெறப்பட்ட துணைக்குழுக்களின் நீளம் சமமாக இருக்கும்?

இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் சராசரிமுள்

 

Ith நிலையில் ஒரு வரிசையை பகிர்வது இடது துணைக்குழுவில் இருக்கும் அந்த வரிசையின் உறுப்புகளின் எண்ணிக்கையையும் குறிக்கிறது.

பெறப்பட்ட துணைக்குழுக்களின் நீளம் சமமாக இருக்க வேண்டும் என்பதை நாம் அறிவோம்

partitionA + partitionB = (நீளம் (A) + நீளம் (B) +1) / 2

(இறுதியாக ஒன்றிணைக்கப்பட்ட வரிசைப்படுத்தப்பட்ட வரிசையின் நீளம் ஒற்றைப்படை என்றால், இடது துணைக்குழுவில் அதிக கூறுகள் இருக்கும்)

இப்போது மீதமுள்ள ஒரே விஷயம் என்னவென்றால், கொடுக்கப்பட்ட இரண்டு வரிசைகளை எவ்வாறு பகிர்வது என்பதை சரிபார்க்க வேண்டும், அதாவது வலது துணைக்குழு இடது துணைக்குழுவை விட அதிகமாக உள்ளது.

வரிசைப்படுத்தப்பட்ட வரிசைகளின் சரியான பகிர்வை வரையறுப்போம்:

எங்களிடம் வரிசை A (நீளம் n) மற்றும் ஒரு வரிசை B (நீளம் மீ) இருப்பதாகக் கூறலாம்

இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் சராசரிமுள்

 

நாம் A இல் i மற்றும் B ஐ j இல் பகிர்வு செய்துள்ளோம்

ஒரு சரியான பகிர்வு எப்போது:

  • 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 இன் பகிர்வின் இடதுபுறத்தில் சில கூறுகள் உள்ளன, அவை பெரிய (வலது) துணைக்குழுவில் வைக்கப்பட வேண்டும். அவ்வாறான நிலையில், நான் இடதுபுறமாகவும், ஜே வலதுபுறமாகவும் நகருவோம்.

B [j-1]> A [i] என்றால், B இன் பகிர்வின் இடதுபுறத்தில் சில கூறுகள் உள்ளன, அவை பெரிய (வலது) துணைக்குழுவில் வைக்கப்பட வேண்டும். அவ்வாறான நிலையில், நாம் j ஐ இடதுபுறமாகவும் நான் வலதுபுறமாகவும் நகர்த்துவோம்.

இப்போது எங்கள் பகிர்வு சுட்டிகளை நகர்த்த நாம் பைனரி தேடலைப் பயன்படுத்தலாம்.

விளக்கம்

அதை ஒரு எடுத்துக்காட்டுடன் புரிந்துகொள்வோம்:

இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகள் A மற்றும் B கொடுக்கப்பட்டுள்ளன.

பகிர்வுகளைத் தொடங்குவோம் பைனரி தேடலைப் பயன்படுத்தி ஒரு சரியான பகிர்வைப் பெற முடியுமா இல்லையா என்பதைச் சரிபார்க்கவும்.

படி 1

இடது = 0

வலது = 6

mid = (0 + 6) / 2 = 3 (A க்கான பகிர்வு)

பகிர்வு A + partitionB = (நீளம் (A) + நீளம் (B) +1) / 2 ஐப் பயன்படுத்தி B இன் பகிர்வை நாம் பெறலாம்

partitionB = (6 + 4 + 1) / 2 - partitionA

பகிர்வு B = 5-3 = 2

முள்

B இன் பகிர்வின் இடது A இன் பகிர்வின் வலதுபுறத்தை விட அதிகமாக உள்ளது. இதன் பொருள் சரியான பகிர்வுக்கு A இன் கூடுதல் கூறுகளை நாம் சேர்க்க வேண்டும்.

படி 2

இடது = நடு + 1 அதாவது இடது = 4 செய்யுங்கள்

வலது = 6

எனவே புதிய நடுப்பகுதி = (4 + 6) / 2 = 5

partitionB = (6 + 4 + 1) / 2 - partitionA

பகிர்வு பி = 0

முள்

A இன் பகிர்வின் இடதுபுறம் B இன் பகிர்வின் வலதுபுறத்தை விட அதிகமாக உள்ளது. சரியான பகிர்வைப் பெற B இன் கூடுதல் கூறுகளை நாம் சேர்க்க வேண்டும் என்பதே இதன் பொருள்.

படி 3

வலதுபுறம் செய்யுங்கள் = நடுப்பகுதி 1

இடது = 4

வலது = 4

எனவே புதிய நடுப்பகுதி = (4 + 4) / 2 = 4

partitionB = (6 + 4 + 1) / 2 - partitionA

பகிர்வு பி = 1

முள்

மூடப்பட்ட உருவத்தில் மொத்தம் 5 கூறுகளும் அதற்கு வெளியே மொத்த 5 கூறுகளும் இருப்பதை இப்போது காணலாம்.

மேலும், A இன் பகிர்வின் இடதுபுறம் B இன் பகிர்வின் வலப்பக்கத்தை விட குறைவாக உள்ளது.

B இன் பகிர்வின் இடது A இன் பகிர்வின் வலப்பக்கத்தை விட குறைவாக உள்ளது.

மேலும் காண்க
இரட்டிப்பாக இணைக்கப்பட்ட பட்டியலைப் பயன்படுத்தி டெக் செயல்படுத்தல்

எனவே எங்கள் வரிசை இதுபோன்று ஒன்றிணைக்கும்:

முள்

எங்கள் வரிசை சம அளவு என்பதால், இறுதி வரிசைப்படுத்தப்பட்ட வரிசையின் நடுத்தர இரண்டு கூறுகளை சராசரியாக எடுத்துக்கொள்வதன் மூலம் சராசரி பெறப்படும்:

  • ஒன்று சரியான பகிர்வின் இடது பக்கத்தின் அதிகபட்சமாக இருக்கும், அதாவது அதிகபட்சம் (17,11).
  • இரண்டாவது சரியான பகிர்வின் வலது பக்கத்தின் குறைந்தபட்சமாக இருக்கும், அதாவது நிமிடம் (19,18).

இல்லையா?

பெறப்பட்ட சராசரி = (17 + 18) / 2

= 17.5

ஒன்றிணைக்கப்பட்ட வரிசைப்படுத்தப்பட்ட வரிசையின் நீளம் ஒற்றைப்படை என்றால், பதில் சரியான பகிர்வின் இடது பக்கத்தின் அதிகபட்சமாக இருக்கும்.

உதாரணமாக

உள்ளீடு:

உள்ளீட்டின் முதல் வரிசையில் n மற்றும் m ஆகிய இரண்டு முழு எண்கள் உள்ளன, இது வரிசை A மற்றும் B இன் அளவைக் குறிக்கிறது.

அடுத்த வரியில் n விண்வெளி பிரிக்கப்பட்ட முழு எண்கள் உள்ளன, அவை A [i] ஐக் குறிக்கும் 0 <= i

அடுத்த வரியில் m இடத்தால் பிரிக்கப்பட்ட முழு எண்கள் உள்ளன, அவை 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

இரண்டு வரிசைப்படுத்தப்பட்ட வரிசைகளின் இடைநிலைக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது: ஓ (பதிவு (என்))

மேலும் காண்க
பாஸ்கல் முக்கோண லீட்கோட்

ஒவ்வொரு அடியிலும், நாங்கள் தேடல் இடத்தை பாதியாக குறைக்கிறோம் (இடது தேடல் இடத்தை அல்லது நடுத்தர குறியீட்டிலிருந்து வலது தேடல் இடத்தைத் தேர்ந்தெடுப்பது).

விண்வெளி சிக்கலானது: ஓ (1) ஏனெனில் நாம் கணக்கீட்டிற்கு சில மாறிகள் பயன்படுத்துகிறோம்.

வாசித்ததற்கு நன்றி!!

குறிப்புகள்