ஒரு வரிசையின் இரண்டு துணைக்குழுக்களின் அதிகபட்ச வேறுபாடு  


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அட்லாசியன் காடென்ஸ் இந்தியா டைரக்டி ஃப்ரீசார்ஜ் வேலை PayU SnapChat டைம்ஸ் இணையம் Xome
அணி ஹாஷ் வரிசையாக்க

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

பின்பற்ற வேண்டிய நிபந்தனைகள்:

  • ஒரு வரிசையில் மீண்டும் மீண்டும் கூறுகள் இருக்கலாம், ஆனால் ஒரு தனிமத்தின் அதிக அதிர்வெண் 2 ஐ விட அதிகமாக இருக்கக்கூடாது.
  • நீங்கள் இரண்டு துணைக்குழுக்களை உருவாக்க வேண்டும், இதனால் அந்தந்த உறுப்புகளின் கூட்டுத்தொகைக்கு இடையிலான வேறுபாடு அதிகபட்சமாக இருக்கும்.
  • வரிசையின் அனைத்து கூறுகளும் எந்த உறுப்புகளையும் விட்டுவிடாமல் இரண்டு துணைக்குழுக்களுக்கு இடையில் பிரிக்க வேண்டும்.
  • ஒரு துணைக்குழுவுக்குள் இரண்டு கூறுகள் ஒரே மாதிரியாக இருக்கக்கூடாது.

உதாரணமாக  

ஒரு வரிசையின் இரண்டு துணைக்குழுக்களின் அதிகபட்ச வேறுபாடு

arr[] = {2, 5, -3, -1, 5, 7}
13

விளக்கம்

துணைக்குழு → (2, 7, 5) - (-3, -1, 5) = 13

{1, 5, 3, -1, -5, 6}
21

விளக்கம்

துணைக்குழு → (1, 3, 5, 6) - (-5, -1) = 21

அல்காரிதம்  

  1. இரண்டை அறிவிக்கவும் வரைபடங்கள், ஒன்று நேர்மறை மற்றும் ஒன்று எதிர்மறை உறுப்பு.
  2. நேர்மறையான கூறுகளையும் அவற்றின் எண்ணிக்கையையும் ஒரே வரைபடத்தில் சேமிக்கவும்.
  3. அதிர்வெண் 1 ஐக் கொண்ட அனைத்து நேர்மறையான கூறுகளையும் சேர்த்து, அதை சேமித்து வைக்கவும் துணைக்குழு 1.
  4. எதிர்மறை உறுப்பு மற்றும் அதன் எண்ணிக்கையை மற்றொரு வரைபடத்தில் சேமிக்கவும்.
  5. அதிர்வெண் 1 ஐக் கொண்ட அனைத்து எதிர்மறை கூறுகளையும் சேர்த்து அதை சேமித்து வைக்கவும் துணைக்குழு 2.
  6. துணைக்குழு 1-துணைக்குழு 2 ஐத் திரும்புக.

விளக்கம்

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

மேலும் காண்க
ஒரே எழுத்துக்கள் கொண்ட குழு சொற்கள்

நாங்கள் ஒரு வரிசை மற்றும் வரைபடத்தை எடுப்போம். வரிசையின் ஒவ்வொரு உறுப்புகளையும் தேர்ந்தெடுத்து அது 0 ஐ விட அதிகமாக இருக்கிறதா என்று சோதிக்கப் போகிறோம். பின்னர் அதை அதன் நிகழ்வுகளின் எண்ணிக்கையுடன் வரைபடத்தில் சேமிக்கப் போகிறோம். நேர்மறை கூறுகளின் அதிர்வெண்களை சேமித்த பிறகு, 0 ஐ விட அதிகமான மற்றும் 1 மட்டுமே அதிர்வெண் கொண்ட ஒரு வரிசையின் அனைத்து மதிப்புகளையும் நாம் சேர்க்கப் போகிறோம், அதாவது பல முறை அல்லது ஒன்றுக்கு மேற்பட்ட முறை வரும் அந்த கூறுகளை நாம் புறக்கணிக்க வேண்டும்.

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

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

குறியீடு  

ஒரு வரிசையின் இரண்டு துணைக்குழுக்களின் அதிகபட்ச வேறுபாட்டைக் கண்டறிய சி ++ குறியீடு

#include<iostream>
#include<unordered_map>

using namespace std;

int maxDiff(int arr[], int n)
{
    unordered_map<int, int> positiveElement;
    unordered_map<int, int> negativeElement;

    int sumSubset1 = 0, sumSubset2 = 0;
    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0)
            positiveElement[arr[i]]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0 && positiveElement[arr[i]] == 1)
            sumSubset1 += arr[i];

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0)
            negativeElement[abs(arr[i])]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0 &&
                negativeElement[abs(arr[i])] == 1)
            sumSubset2 += arr[i];

    return abs(sumSubset1 - sumSubset2);
}
int main()
{
    int arr[] = {2,5,-3,-1,5,7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference found is: " << maxDiff(arr, n);
    return 0;
}
Maximum difference found is: 13

ஒரு வரிசையின் இரண்டு துணைக்குழுக்களின் அதிகபட்ச வேறுபாட்டைக் கண்டறிய ஜாவா குறியீடு

import java.util.HashMap;
class SubsetDifference
{
    public static int getDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> positiveElement=new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> negativeElement=new HashMap<Integer, Integer>();
        int sumSubset1 = 0, sumSubset2 = 0;
        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] > 0)
            {
                if(positiveElement.containsKey(arr[i]))
                    positiveElement.put(arr[i],positiveElement.get(arr[i])+1);
                else
                    positiveElement.put(arr[i],1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] > 0 && positiveElement.get(arr[i]) == 1)
                sumSubset1 += arr[i];

        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] < 0)
            {
                if(negativeElement.containsKey(Math.abs(arr[i])))
                    negativeElement.put(Math.abs(arr[i]),negativeElement.get(Math.abs(arr[i]))+1);
                else
                    negativeElement.put(Math.abs(arr[i]),1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] < 0 && negativeElement.get(Math.abs(arr[i]))== 1)
                sumSubset2 += arr[i];

        return Math.abs(sumSubset1 - sumSubset2);
    }
    public static void main(String [] args)
    {
        int arr[] = {2,5,-3,-1,5,7};
        int n = arr.length;
        System.out.println("Maximum difference found is:"+getDifference(arr, n));
    }
}
Maximum difference found is:13

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

நேர சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. நாங்கள் ஹாஷ்மேப்பைப் பயன்படுத்தியதால், ஓ (1) இல் செருக / நீக்குதல் / தேடலைச் செய்ய முடிகிறது.

மேலும் காண்க
ஒவ்வொரு எழுத்துக்குறி மாற்று வினவலுக்கும் பிறகு பாலிண்ட்ரோம் சரிபார்க்கவும்

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.