Ավելացվող տարրեր այնպես, որ տիրույթի բոլոր տարրերը զանգվածում լինեն


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են GreyOrange Կուլիզա Snapdeal Սինոփսիս Տերադատա Times ինտերնետ
Դասավորություն Խանգարել Հեշինգ դասավորում

Խնդիրի հայտարարություն

«Ավելացվող տարրերը այնպես, որ տիրույթի բոլոր տարրերը զանգվածում լինեն» նշում է, որ ձեզ տրվում է ամբողջ թվերի զանգված: Խնդիրի հայտարարությունը խնդրում է պարզել զանգվածում ավելացվող տարրերի քանակը, որպեսզի բոլոր տարրերը ընկած լինեն [X, Y] տիրույթում ներառյալ գոնե մեկ անգամ զանգվածում: X և Y համապատասխանաբար զանգվածի նվազագույն և առավելագույն թվերն են:

Օրինակ

arr[] = {4,5,7,9,11}
3

Բացատրություն. X- ը և Y- ը 4-ն են և 11-ը (համապատասխանաբար նվազագույն և առավելագույն թվեր), այս թվերի սահմաններում միայն 3-ին է պակասում 6, 8 և 10:

Ավելացվող տարրեր այնպես, որ տիրույթի բոլոր տարրերը զանգվածում լինեն

arr[] = {2,4,6,7}
2

Բացատրություն. X- ը և Y- ը 2 և 7 են (համապատասխանաբար նվազագույն և առավելագույն թվեր), այս թվերի սահմաններում միայն 2-ին է պակասում 3-ը և 5-ը:

Լրացուցիչ տարրեր գտնելու ալգորիթմ ՝ այնպես, որ տիրույթի բոլոր տարրերը զանգվածում լինեն

1. Declare a Set.
2. Set output to 0, minValue to the maximum value of integer and maxValue to the minimum value of an integer.
3. Traverse the array and put all the values into the set and simultaneously find out the maximum and the minimum number of an array and store it to the maxValue and minValue respectively.
4. Traverse the array again, from minValue to maxValue.
5. Check if the map doesn’t contain any of the elements in traversal, then, increase the count of output.
6. Return output.

բացատրություն

Մենք ունենք ամբողջ թիվ զանգված Խնդիրն այն է, որ պարզվի զանգվածում ավելացվող տարրերի քանակը: Այնպես որ, բոլոր տարրերը գտնվում են զանգվածի առավելագույն և նվազագույն թվերի տիրույթում, որպեսզի ոչ մի տարր գոնե մեկ անգամ չպետք է առաջանա:

Հայտարարել հավաքածու, Սեթը հատկություն ունի միայն մեկ անգամ հստակ տարրեր պահելու համար: Սա նշանակում է, որ այն հեռացնում է ընդհանուր տարրերը և պահում է միայն հստակ տարրեր: Այսպիսով, մենք կկարողանանք կարգավորել այդ գործը: Այժմ մենք մտնելու ենք զանգվածի բոլոր տարրերը հավաքածուի մեջ: Միաժամանակ մենք կբացահայտենք առավելագույն և նվազագույն տարրը: Որպեսզի ստիպված չլինենք լրացուցիչ անցում կատարել `պարզելու առավելագույնը և մինուսը: Ի վերջո, մենք պարզապես պետք է պարզենք միջակայքում բացակայող տարրերի քանակը: Այսպիսով, միայն թվերը հաշվելու անհրաժեշտություն կա: Եվ պետք չէ գործ ունենալ թվերի հետ:

Այժմ մենք կկողմնորոշենք զանգվածը ՝ սկսած զանգվածի նվազագույն արժեքից մինչև զանգվածի առավելագույն արժեքը: Քանի որ սա մեզ անհրաժեշտ միակ տիրույթն է: Մենք կընտրենք տիրույթում ընդգրկված թվերից յուրաքանչյուրը և ստուգենք ՝ արդյոք հավաքածուն չունի այդ տիրույթի արժեքը: Եթե ​​հավաքածուն չի պարունակում այդ ընթացիկ միջակայքի արժեքը, ապա մենք պատրաստվում ենք ավելացնել արտադրանքի քանակը: Եվ ամեն անգամ, երբ արտադրանքի արժեքը կավելացնենք 1-ով, երբ հավաքածուում տիրույթի արժեք ներկայումս չկա: Ասես նշված կոդում նվազագույնը 4 է, իսկ առավելագույնը ՝ 11, և այդ միջակայքում բացակայում են 6,8-ը և 10-ը (4,11), նույնպես այս տարրերը զանգվածում չկան, ուստի կհաշվի տարրերի այդ քանակը: Եվ վերջապես, մենք կվերադարձնենք այդ արդյունքը:

Կոդ

C ++ կոդ ՝ ավելացնելու համար տարրեր գտնելու համար, որպեսզի ընդգրկույթի բոլոր տարրերը լինեն զանգվածում

#include<iostream>
#include<unordered_set>

using namespace std;

int getCountMissingNumber(int arr[], int n)
{
    unordered_set<int> SET;
    int output = 0;
    int maxValue = INT_MIN;
    int minValue = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        SET.insert(arr[i]);
        if (arr[i] < minValue)
            minValue = arr[i];
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    for (int a = minValue; a <= maxValue; a++)
    {
        if (SET.find(a) == SET.end())
        {
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {4,5,7,9,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getCountMissingNumber(arr, n);
    return 0;
}
3

Java- ի ծածկագիրը `տարրերը ավելացնելու համար, որպեսզի ընդգրկույթի բոլոր տարրերը լինեն զանգվածում

import java.util.HashSet;

class NumberBwRange
{
    public static int getCountMissingNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<>();
        int output = 0;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
            if (arr[i] < minValue)
                minValue = arr[i];
            if (arr[i] > maxValue)
                maxValue = arr[i];
        }

        for (int i = minValue; i <= maxValue; i++)
            if (!SET.contains(i))
                output++;
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 4,5,7,9,11 };
        int n = arr.length;
        System.out.println(getCountMissingNumber(arr, n));
    }
}
3

Բարդության վերլուծություն

Timeամանակի բարդություն

O (առավելագույնը - րոպե + 1) որտեղ «Մաքս» և «Րոպե» են առավելագույնը և նվազագույն զանգվածի արժեքը: Քանի որ մենք անցնում էինք նվազագույն տարրից առավելագույն տարր: Այդ պատճառով ամենավատ դեպքում այս արժեքը կարող է գերազանցել N տարրերը: Այսպիսով, քանի որ max-min + 1 կարող է ավելի մեծ լինել, քան N. timeամանակի բարդությունը O է (max-min + 1), որտեղ max- ը նշանակում է առավելագույն տարրը, իսկ min- ը `նվազագույն տարրը:

Տիեզերական բարդություն

ՎՐԱ) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք պահպանում ենք միայն N տարրեր, ալգորիթմը գծային տիեզերական բարդություն ունի: