عناصر از دست رفته محدوده را پیدا کنید  


سطح دشواری ساده
اغلب در تحویل کالا خاکستری نارنجی لینک ناگارو اپرا Synopsys
مخلوط لارسن و توبرو مرتب سازی

مسئله پیدا کردن عناصر گمشده در یک محدوده "بیان می کند که به شما داده می شود صف از عناصر متمایز در یک محدوده خاص و محدوده ای به عنوان کم و زیاد ارائه شده است. تمام عناصر گمشده را در محدوده ای پیدا کنید که در آرایه ای وجود ندارد. خروجی باید به ترتیب مرتب شده باشد.

مثال  

عناصر از دست رفته محدوده را پیدا کنیدسنجاق

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

توضیح

اینها اعداد گمشده در آرایه در محدوده داده شده به صورت کم و زیاد است ، یعنی 1 و 10.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

توضیح

اینها اعداد گمشده در آرایه در محدوده داده شده به صورت کم و زیاد است ، یعنی 1 و 10.

الگوریتم  

  1. اعلام الف تنظیم.
  2. آرایه را رد کنید و همه عناصر را در مجموعه قرار دهید.
  3. در حالی که "i" برابر با کم و "i" کمتر از برابر زیاد است.
    • اگر مجموعه ای حاوی "i" نباشد.
      • "i" را چاپ کنید.

توضیح

به ما یک عبارت مسئله ای داده شده است که می خواهد تمام عناصر گمشده در یک آرایه را در یک محدوده مشخص و کم و زیاد پیدا کند. برای حل این ما از یک مجموعه استفاده خواهیم کرد و مقادیر را در مجموعه آرایه داده شده ذخیره خواهیم کرد. به ما محدوده ای کم و زیاد داده می شود ، ما باید همه عناصر را به صورت کم و زیاد چاپ کنیم.

همچنین مشاهده کنید
سکانس گلومب

برای بدست آوردن این سفارش ما از قبل عناصر آرایه را در مجموعه ذخیره می کنیم. ما نیاز به اجرای یک حلقه داریم که مقدار "i" را کم می کند. حلقه را اجرا می کنیم تا زمانی که مقدار "i" زیاد شود. سپس بررسی کنید که آیا مجموعه حاوی مقدار "i" نیست سپس "i" را چاپ کنید. از این رو تمام عناصری را که در یک آرایه از دست رفته اند ، در یک محدوده مشخص دریافت خواهیم کرد. اجازه بدین مثالی را مطرح کنیم.

arr [] = {2 ، 3 ، 7 ، 8} کم = 1 ، زیاد = 9

ما باید آرایه را رد کنیم و تمام عناصر آرایه را در مجموعه قرار دهیم. مجموعه ما خواهد شد

مجموعه = [2,3,7,8،XNUMX،XNUMX،XNUMX]

در یک حلقه مقدار i را به مقدار کم مقدار دهی می کند و حلقه تا زیاد اجرا می شود ، به این معنی است که "من" برابر با کم = 1 و زیاد = 9 است

i = 1 ، اگر مجموعه شامل i نباشد ، شماره 1 را چاپ می کند

[1]

من = 2 ، مجموعه دارای مقدار "2" است و هیچ کاری انجام نمی دهد.

من = 3 ، مجموعه دارای مقدار "3" است و هیچ کاری انجام نمی دهد.

i = 4 ، اگر مجموعه شامل i نباشد ، شماره 4 را چاپ می کند

[1، 4]

i = 5 ، اگر مجموعه شامل i نباشد ، شماره 5 را چاپ می کند

[1، 4، 5]

i = 6 ، اگر مجموعه شامل i نباشد ، شماره 6 را چاپ می کند

[1 ، 4 ، 5 ، 6]

من = 7 ، مجموعه دارای مقدار "7" است و هیچ کاری انجام نمی دهد.

من = 8 ، مجموعه دارای مقدار "8" است و هیچ کاری انجام نمی دهد.

i = 9 ، اگر مجموعه شامل i نباشد ، شماره 1 را چاپ می کند

[1 ، 4 ، 5 ، 6 ، 9]

خروجی ما تبدیل خواهد شد: [1 ، 4 ، 5 ، 6 ، 9]

رمز  

کد ++ C برای یافتن عناصر از دست رفته محدوده

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

کد جاوا برای یافتن عناصر از دست رفته محدوده

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

تحلیل پیچیدگی  

پیچیدگی زمان

O (n + (بسیار کم + 1)) جایی که "n" تعداد عناصر موجود در آرایه است ، "بالا" و "کم" ورودی ارائه شده است.

همچنین مشاهده کنید
طول بزرگترین زیر مجموعه با عناصر مجاور

پیچیدگی فضا

بر)، اگر همه عناصر از هم متمایز باشند ، در بدترین حالت ما باید تمام عناصر را ذخیره کنیم. بنابراین ساخت الگوریتم به زمان خطی نیاز دارد.