Мужийн бүх элементүүд массивт байхаар нэмэх элементүүд


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Саарал улбар шар Кулиза Snapdeal Синопсис Teradata Times Интернет
Array Хаш Хаширч байна Ангилах

Асуудлын мэдэгдэл

“Мужийн бүх элементүүд массивт байхаар нэмэх элементүүд” гэж танд бүхэл тоон массивыг өгч байгаа гэсэн үг юм. Асуудлын шийдэл нь бүх элементүүд [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.

Тайлбар

Бидэнд байгаа бүхэл тоо массив. Асуудал нь массивт нэмэх элементийн тоог олох явдал юм. Бүх элементүүд массивын хамгийн их ба хамгийн бага тооны хязгаарт байх бөгөөд ингэснээр дор хаяж нэг удаа ямар ч элемент гарах ёсгүй.

Set-ийг зарлах, Set нь ялгаатай элементүүдийг зөвхөн нэг удаа хадгалах шинж чанартай байдаг. Энэ нь нийтлэг элементүүдийг арилгаж, зөвхөн ялгаатай элементүүдийг хадгална гэсэн үг юм. Тиймээс бид энэ хэргийг шийдвэрлэх боломжтой болно. Одоо бид массивын бүх элементүүдийг багцад оруулах болно. Үүний зэрэгцээ бид хамгийн их ба хамгийн бага элементийг олж мэдэх болно. Хамгийн их ба минутыг олохын тулд бид нэмэлт траверс хийх шаардлагагүй болно. Эцсийн эцэст бид хүрээн дэх алга болсон элементүүдийн тоог олох хэрэгтэй. Тиймээс зөвхөн тоонуудыг тоолох шаардлагатай байна. Бид тоонуудтай өөрсдөө харьцах шаардлагагүй болно.

Одоо бид массивын хамгийн бага утгаас массивын хамгийн дээд утга хүртэл массивыг туулах болно. Энэ бол бидэнд хэрэгтэй цорын ганц хүрээ юм. Бид муж доторх тоо тус бүрийг сонгож, багцад энэ мужийн утга байхгүй эсэхийг шалгана. Хэрэв тухайн багцад тухайн тухайн мужийн утга ороогүй бол бид гаралтын тоог нэмэгдүүлэх болно. Тэр бүрт бид олонлогод хүрэхгүй муж бүрийн гаралтын утгыг 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (хамгийн их - мин + 1) хаана “Max” болон “Мин” байна хамгийн их болон хамгийн бага массивын утга. Бид хамгийн бага элементээс хамгийн их элемент рүү шилжсэн тул. Тийм ч учраас хамгийн муу тохиолдолд энэ утга N элементээс хэтэрч магадгүй юм. Тиймээс max-min + 1 нь N-ээс их байж болох тул цаг хугацааны нарийн төвөгтэй байдал нь O (max-min + 1) бөгөөд max нь хамгийн их элементийг, min нь хамгийн бага элементийг илэрхийлнэ.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Бид зөвхөн N элементийг хадгалж байгаа тул алгоритм нь шугаман орон зайн нарийн төвөгтэй байдаг.