Массивтің екі ішкі жиынының мүмкін болатын айырымы  


Күрделілік дәрежесі қиын
Жиі кіреді Atlassian Cadence Үндістан Directi FreeCharge опера PayU Snapchat Times Интернет Xome
Array Hash Сұрыптау

Айталық, бізде бүтін сан массив. «Массивтің екі ішкі жиынының мүмкін болатын айырмасы» деген есептер жиымның екі ішкі жиыны арасындағы мүмкін болатын максималды айырмашылықты табуды сұрайды.

Орындалатын шарттар:

  • Массивте қайталанатын элементтер болуы мүмкін, бірақ элементтің ең жоғары жиілігі 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-ге тең элементтер болатындығы туралы шарттың қорытындысын алғаннан кейін, біз қосындының айырымын да қайтаруымыз керек, ал бұл біздің жауабымыз болар еді.

код  

Массивтің екі жиынының максималды мүмкін айырмашылығын табу үшін 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

Массивтің екі жиынының максималды айырмашылығын табу үшін Java коды

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

Күрделілікті талдау  

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз HashMap қолданғандықтан, O (1) ішіне кірістіру / жою / іздеуді жүзеге асыра аламыз.

Сондай-ақ, қараңыз
Әр таңбаны ауыстырғаннан кейін Палиндромды тексеріңіз

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.