एर्रेको दुई उपसमूहहरूको अधिकतम सम्भव भिन्नता


कठिनाई तह हार्ड
बारम्बार सोधिन्छ Atlassian ताल भारत Directi फ्रीचार्ज ओपेरा PayU Snapchat टाइम्स इन्टरनेट Xome
एरे हैश क्रमबद्ध

मानौं, हामीसँग छ पूर्णांक array। समस्या कथन "एर्रेको दुई उपसमूहको अधिकतम सम्भावित फरक" ले एर्रेको दुई उप-सहायकहरू बीच अधिकतम सम्भव भिन्नता पत्ता लगाउन सोध्छ।

सर्तहरू पछ्याउनु पर्ने:

  • एर्रेमा दोह्याउने तत्त्वहरू समावेश हुन सक्छ, तर तत्वको उच्च आवृत्ति २ भन्दा ठूलो हुनुहुन्न।
  • तपाईंले दुई उपसमूह बनाउनु पर्छ ताकि उनीहरूको सम्बन्धित तत्वहरूको योग बीच भिन्नता अधिकतम हो।
  • एर्रेका सबै एलिमेन्टहरू कुनै पनि पछाडि कुनै तत्वलाई नछोडी दुई उपसमूह बीचमा विभाजन गरिनु पर्दछ।
  • सबसेटमा दुई तत्वहरू समान हुँदैनन्।

उदाहरणका

एर्रेको दुई उपसमूहहरूको अधिकतम सम्भव भिन्नता

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

स्पष्टीकरण

सबसेट → (२,,,)) - (-2, -१,)) = १ 7

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

स्पष्टीकरण

सबसेट → (१,,,,,)) - (-1, -१) = २१

अल्गोरिदम

  1. दुई घोषणा गर्नुहोस् नक्सा, एक सकारात्मकको लागि र एक नकारात्मक तत्वको लागि।
  2. सकरात्मक तत्व र तिनीहरूको गणना एक नक्सामा भण्डार गर्नुहोस्।
  3. सबै सकरात्मक तत्वहरू थप्दै गर्नुहोस् जसमा फ्रिक्वेन्सी १ छ र यसलाई भण्डारण गर्दैछ उपसेट १.
  4. नकारात्मक तत्व भण्डार गर्नुहोस् र अर्को मानचित्रमा यसको गणना।
  5. सबै नकारात्मक तत्वहरू थप्दै गर्नुहोस् जसमा फ्रिक्वेन्सी १ छ र यसलाई भण्डारण गर्दैछ उपसेट १.
  6. उपसेट १-उपसेट २ फिर्ता गर्नुहोस्।

स्पष्टीकरण

हामीले एउटा दिएका छौं array, हामीले दुई उपसमूहको तत्वहरूको योग बीच भिन्नता पत्ता लगाउन आवश्यक छ र त्यो अधिकतम हुनुपर्दछ। हामी एक प्रयोग गर्न जाँदैछन् नक्सा. ह्याशिंग यो प्रश्न समाधान गर्न एक कुशल तरीका प्रदान गर्दछ। हामी दुई नक्शा प्रयोग गर्ने छौं। एक सकारात्मक तत्वहरूमा गरेको अपरेशनहरूको लागि हो र अर्को नकारात्मक तत्वहरूमा। एर्रेमा सकारात्मक र नकारात्मक दुबै तत्वहरू समावेश हुन सक्दछ, त्यसैले हामीले त्यसलाई पनि ह्यान्डल गर्नुपर्दछ।

हामी एर्रे र नक्शा लिनेछौं। हामी एर्रेको प्रत्येक एलिमेन्ट छान्न जाँदैछौं र यो 0. भन्दा ठुलो छ कि छैन जाँच्न जानेछौं। त्यसोभए हामी त्यसलाई नक्सामा भण्डार गर्न जानेछौं यसको उपस्थिति संख्याको साथ। सकारात्मक तत्वहरूको फ्रिक्वेन्सीहरू भण्डारण गरेपछि हामी एउटा एर्रेको सबै मानहरू जोड्न गइरहेका हुन्छौं जुन ० भन्दा ठूलो हुन्छ र केवल १ को फ्रिक्वेन्सी पनि हुन्छ, यसको मतलब हामीले ती तत्वहरूलाई वेवास्ता गर्नु पर्छ जुन धेरै पटक वा धेरै पटक आउँछ।

उस्तै चीज नकारात्मक तत्वहरूको साथ गरिन्छ हामी एउटा एर्रेको प्रत्येक तत्व छान्नेछौं र यस पटक हामी यो जाँच गर्नेछौं कि यो ० भन्दा कम छ कि छैन। हामी यसलाई नक्सामा भण्डार गर्न जाँदैछौं (यसलाई सकारात्मक संख्या बनाउँदै) यसको संख्या सहित। घटनाहरू। नकारात्मक तत्त्वहरूको फ्रिक्वेन्सीहरू भण्डारण गरेपछि, हामी एउटा एर्रेको सबै मानहरू जोड्न लाग्छौं जुन ० भन्दा थोरै हुन्छ र जसको फ्रिक्वेन्सी मात्र १ हुन्छ। यहाँ पनि, हामीले ती तत्वहरू बेवास्ता गर्नु पर्छ जुन धेरै पटक वा धेरै आउँछ। एक पटक भन्दा

सबै सकारात्मक र नकरात्मक तत्त्वहरूको योगफल पाए पछि फ्रिक्वेन्सी १ भएको तत्वहरूको पालना भयो, हामीले दुबै भिन्नताको फर्काउनु पर्छ र त्यो हाम्रो उत्तर हो।

कोड

C ++ कोड एर्रेको दुई उपसमूहहरूको अधिकतम सम्भावित भिन्नता फेला पार्न

#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" एर्रेमा एलिमेन्ट्सको संख्या हो।