Массивын Leetcode шийдлээс алга болсон бүх тоог олох


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg Google-ийн Microsoft- Yahoo
Array Хаширч байна

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

Энэ асуудалд бидэнд массив бүхэл тоонууд. Энэ нь 1-ээс N хүртэлх элементүүдийг агуулдаг бөгөөд N = массивын хэмжээ. Гэсэн хэдий ч алга болсон зарим элементүүд байгаа бөгөөд зарим давхардсан зүйлүүд оронд нь байгаа болно. Бидний зорилго бол алга болсон бүхэл тооны массивыг буцааж өгөх явдал юм.

Жишээ нь

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

Массивын Leetcode шийдлээс алга болсон бүх тоог олох

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

Массивын Leetcode шийдлээс алга болсон бүх тоог олох

Хандалт (HashSet ашиглах)

Бид массив дахь элемент бүрийг тэмдэглээд дараа нь ямар элементүүд алга болсон эсвэл алга болсоныг шалгахын тулд [1, N] мужид давталт хийж болно. Бид бүхэл тоог тэмдэглэсэн эсэхээс үл хамааран хадгалах багцыг ашигладаг.

Алгоритм

  1. Хэш багцыг эхлүүлэх тэмдэг [Бүхэл тоо] байгаа элементүүдийг хадгалах.
  2. Элемент бүрийн хувьд i массивт:
    • нэмэх i to тэмдэг
  3. Жагсаалт / вектор эхлүүлэх үр дүн массив дахь алга болсон элементүүдийг хадгалах
  4. Элемент бүрийн хувьд мужид: [1, N]:
    • If дотор байхгүй байна тэмдэг:
      • Үүнийг нэмнэ үү үр дүн
  5. буцах үр дүн
  6. Үр дүнг хэвлэ

Массивын Leetcode шийдэлд алга болсон бүх тоог олох хэрэгжилт

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;
}

Java програм

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

Массив Leetcode шийдэлд алга болсон бүх тоонуудыг олох цогц шинжилгээ

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

O (N) бүхэл массивыг тэмдэглэхийн тулд бүх массивыг нэг удаа туулахдаа. N = массивын хэмжээ.

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

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

Хандалт (газар дээр нь өөрчлөх)

Энэ асуудалд анхаарах нэг зүйл бол: "массив үргэлж хэмжээнээс бага эсвэл тэнцүү элемент агуулдаг". Энэ нь олон тооны ялгаатай элементүүдийн адил индексүүд байдаг гэсэн үг юм. Түүнчлэн, алга болсон элементүүд нь үргэлж N-ээс бага (массивын хэмжээ) байх болно. Энэхүү хязгаарлалтыг ашиглан массивыг өөрөө ашиглаж бүхэл тоон хэмжээг ямар нэгэн байдлаар хадгалах боломжтой. Жишээлбэл, бид бичиж чадна гэж бодъё Үнэн худал элементийн индекс дээр байгаа / байхгүйг тус тус тэмдэглэнэ. Манай тохиолдолд массив нь аль хэдийн элемент агуулсан байдаг тул ийм төрлийн хадгалах / санах нь боломжгүй юм шиг санагддаг. Гэсэн хэдий ч бүх элементүүд эерэг гэдгийг бид мэддэг тул “сөрөг” -ийг массив дотор элемент харсан, хараагүй гэсэн тэмдэг болгон ашиглаж болно. Ашиглан зарим индекс дээр хадгалагдсан бодит утгыг авах боломжтой гэдгийг анхаарна уу үнэмлэхүй () бүхэл тооны үнэмлэхүй утгыг буцаах функц. Ийм байдлаар массивыг хэш газрын зураг болон контейнер болгон ашиглаж болно.

Жишээлбэл, хэрэв бид массивт '2' элементийг харсан бол Array [1] = -1 * Array [1] -г зааж өгч болох бөгөөд энэ нь массив дээр 2-р элемент харагдаж байгааг бидэнд хэлэх болно.

Энэ заль мэх нь индекс дээр байгаа элементийг харсан тохиолдолд хадгалах массивыг ашиглах болно i. Хийж дууссаны дараа бид сөрөг бус бүхэл тоог олохын тулд [1, N] мужид давталт хийж, шаардлагатай үр дүнг хэвлэе. Энэ нь зөвхөн бид байгаа тохиолдолд л боломжтой гэдгийг анхаарна уу зөвшөөрөгдсөн массивыг өөрчлөх.

Алгоритм

  1. Элемент бүрийн хувьд массивт:
    • Хэрэв массив [i - 1]> 0 бол:
      • Үүнийг сөрөг гэж тохируул, эсвэл, Массив [i - 1] * = -1;
  2. Жагсаалт / вектор эхлүүлэх үр дүн алга болсон бүх элементүүдийг хадгалах
  3. Бүхэл тоо [1, N] мужид (N = массивын хэмжээ):
    • If Массив [i]> 0
      • Энэ элементийг нэмнэ үү i to үр дүн
  4. буцах үр дүн
  5. Үр дүнг хэвлэ

Массивын Leetcode шийдэлд алга болсон бүх тоог олох хэрэгжилт

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;
}

Java програм

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

Массив Leetcode шийдэлд алга болсон бүх тоонуудыг олох цогц шинжилгээ

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

O (N) алга болсон элементүүдийг олохын тулд оролтоос үл хамааран массивын хоёр дамжуулалтыг ажиллуулдаг. N = массивын хэмжээ.

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

O (1) Бид байнгын санах ойн зайг ашигладаг тул.