پیدا کردن همه اعداد ناپدید شده در یک راه حل کد کد آرایه


سطح دشواری ساده
اغلب در خشت آمازون سیب بلومبرگ گوگل مایکروسافت یاهو
صف هشی کردن

بیان مسأله

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

مثال

Array = {1 , 2 , 5 , 6 , 2 , 5}
3 4

پیدا کردن همه اعداد ناپدید شده در یک راه حل کد کد آرایه

Array = {1 , 2 , 3 , 4}
n

پیدا کردن همه اعداد ناپدید شده در یک راه حل کد کد آرایه

رویکرد (با استفاده از HashSet)

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

الگوریتم

  1. شروع یک مجموعه هش علامت [عدد صحیح] برای ذخیره عناصر موجود
  2. برای هر عنصر i در آرایه:
    • اضافه کردن i به علامت
  3. لیست / بردار را آغاز کنید نتیجه برای ذخیره عناصر از دست رفته در آرایه
  4. برای هر عنصر در محدوده: [1 ، N]:
    • If در وجود ندارد علامت گذاری:
      • آن را به اضافه کنید نتیجه
  5. برگشت نتیجه
  6. نتیجه را چاپ کنید

پیاده سازی یافتن همه اعداد ناپدید شده در یک راه حل کد کد آرایه

برنامه C ++

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

برنامه جاوا

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}
3 4

تجزیه و تحلیل پیچیدگی یافتن همه شماره های ناپدید شده در یک راه حل کد کد آرایه

پیچیدگی زمان

بر) همانطور که یکبار کل آرایه را رد می کنیم تا عدد صحیح را علامت گذاری کنیم. N = اندازه آرایه.

پیچیدگی فضا 

بر) همانطور که تمام اعداد موجود در آرایه را در یک جدول هش ذخیره می کنیم. توجه داشته باشید که ما آرایه خروجی را در سهم پیچیدگی فضا در نظر نمی گیریم.

رویکرد (اصلاح در محل)

نکته ای که باید در این مسئله مورد توجه قرار گیرد این است: "آرایه همیشه دارای عناصر کوچکتر یا مساوی با اندازه آن است". این بدان معناست که به تعداد عناصر مجزا شاخص وجود دارد. همچنین ، عناصر از دست رفته همیشه کمتر از N (اندازه آرایه) خواهند بود. با استفاده از این محدودیت ، می توانیم از خود آرایه استفاده کنیم تا به نوعی وجود یک عدد صحیح را ذخیره کنیم. به عنوان مثال ، فرض کنید که ما می توانیم بنویسیم درست غلط در شاخص یک عنصر به ترتیب وجود و عدم حضور آن را نشان می دهد. در مورد ما ، این آرایه از قبل دارای عناصر است ، بنابراین این نوع ذخیره سازی / یادداشت سازی عملی به نظر نمی رسد. با این حال ، از آنجا که می دانیم همه عناصر مثبت هستند ، می توانیم از "منفی" به عنوان نشانه اینکه آیا عنصری را در آرایه دیده ایم یا نه ، استفاده کنیم. توجه داشته باشید که ما می توانیم مقدار واقعی ذخیره شده در برخی از شاخص ها را با استفاده از واکشی کنیم مطلق() تابعی که مقدار مطلق یک عدد صحیح را برمی گرداند. به این ترتیب می توان از آرایه به عنوان یک نقشه هش و هم یک ظرف استفاده کرد.

به عنوان مثال ، اگر عنصر '2' را در آرایه مشاهده کرده باشیم ، می توانیم آرایه [1] = -1 * آرایه [1] را اختصاص دهیم که به ما می گوید عنصر 2 در آرایه دیده می شود.

اگر عنصری را در index مشاهده کنیم ، این ترفند آرایه را در محل ذخیره می کند i. پس از اتمام ، می توانیم یک حلقه را در محدوده [1 ، N] اجرا کنیم تا تمام عددهای صحیح غیر منفی را پیدا کنیم (به این معنی که دیده نشده اند) و از این رو ، نتیجه مورد نظر را چاپ کنیم. توجه داشته باشید که این تنها در صورت وجود ما امکان پذیر است مجاز برای تغییر آرایه

الگوریتم

  1. برای هر عنصر در آرایه:
    • اگر آرایه [i - 1]> 0:
      • این را به صورت منفی تنظیم کنید ، یا ، آرایه [i - 1] * = -1؛
  2. لیست / بردار را آغاز کنید نتیجه برای ذخیره تمام عناصر گمشده
  3. برای هر عدد صحیح در محدوده [1 ، N] (N = اندازه آرایه):
    • If آرایه [i]> 0
      • این عنصر را اضافه کنید i به نتیجه
  4. برگشت نتیجه
  5. نتیجه را چاپ کنید

پیاده سازی یافتن همه اعداد ناپدید شده در یک راه حل کد کد آرایه

برنامه C ++

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

برنامه جاوا

import java.util.*;
import java.lang.Math;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

تجزیه و تحلیل پیچیدگی یافتن همه شماره های ناپدید شده در یک راه حل کد کد آرایه

پیچیدگی زمان

بر) همانطور که دو پاس از آرایه را صرف نظر از ورودی برای یافتن عناصر گمشده اجرا می کنیم. N = اندازه آرایه.

پیچیدگی فضا 

O (1) همانطور که از فضای حافظه ثابت استفاده می کنیم.