Գտեք անհետացած բոլոր թվերը զանգվածի Leetcode լուծման մեջ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg Google Microsoft Անտաշ անասուն նողկալի արարած
Դասավորություն Հեշինգ

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

Այս խնդրում մեզ տրվում է ան դասավորություն ամբողջ թվերի: Այն պարունակում է տարրեր ՝ սկսած 1-ից N, որտեղ N = զանգվածի չափը: Այնուամենայնիվ, կան որոշ տարրեր, որոնք անհետացել են, և որոշ կրկնօրինակներ կան դրանց տեղում: Մեր նպատակն է վերադարձնել այդպիսի բոլոր անհետացած ամբողջ թվերի զանգվածը:

Օրինակ

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

Գտեք անհետացած բոլոր թվերը զանգվածի Leetcode լուծման մեջ

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

Գտեք անհետացած բոլոր թվերը զանգվածի Leetcode լուծման մեջ

Մոտեցում (օգտագործելով HashSet)

Մենք կարող ենք նշել զանգվածի յուրաքանչյուր տարր և այնուհետև շրջանցել տիրույթում. [1, N] ՝ ստուգելու համար, թե որ տարրերն են անհետացել կամ բացակայում զանգվածում: Մենք օգտագործում ենք hash հավաքածու ՝ պահելու համար, թե արդյոք ամբողջ թիվ նշվել է, թե ոչ:

Ալգորիթմ

  1. Նախաձեռնեք հեշ հավաքածու նշում [ամբողջ թիվ] պահելու համար առկա տարրեր:
  2. Յուրաքանչյուր տարրի համար i զանգվածում.
    • Ավելացնել i դեպի նշել
  3. Նախաձեռնեք ցուցակը / վեկտորը արդյունք զանգվածում բացակայող տարրերը պահելու համար
  4. Յուրաքանչյուր տարրի համար միջակայքում ՝ [1, N]:
    • If ներկա չէ նշագծել:
      • Ավելացնել այն արդյունք
  5. Վերադառնալ արդյունք
  6. Տպեք արդյունքը

Rayանգվածի 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

Rayանգվածի Leetcode լուծույթում անհետացած բոլոր թվերի բարդության վերլուծություն

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

ՎՐԱ) երբ մենք ամբողջ զանգվածը հատում ենք մեկ անգամ `ամբողջ թվերը նշելու համար: N = զանգվածի չափը:

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

ՎՐԱ) երբ զանգվածում պահում ենք բոլոր համարները, որոնք առկա են զանգվածում, հեշ աղյուսակում: Նշենք, որ մենք ելքի զանգվածը չենք համարում տարածության բարդության ներդրման մեջ:

Մոտեցում (տեղում փոփոխություն)

Այս խնդրում նկատելի է մեկ կետ. «Զանգվածը միշտ պարունակում է իր չափին պակաս կամ հավասար տարրեր»: Սա նշանակում է, որ կան այնքան ինդեքսներ, որքան շատ տարբեր տարրեր: Բացի այդ, բացակայող տարրերը միշտ պակաս կլինեն N- ից (զանգվածի չափը): Օգտագործելով այս կաշկանդումը, մենք կարող ենք օգտագործել զանգվածը `ինչ-որ կերպ ամբողջ թվերի ամբողջությունը պահելու համար: Օրինակ, ենթադրենք, որ մենք կարող ենք գրել ճիշտ է կեղծ է տարրի ցուցիչում համապատասխանաբար նշելու դրա առկայությունը / բացակայությունը: Մեր դեպքում, զանգվածն արդեն պարունակում է տարրեր, ուստի պահպանումն / հիշողությունը պահելը նման իրատեսական չի թվում: Այնուամենայնիվ, քանի որ մենք գիտենք, որ բոլոր տարրերը դրական են, մենք կարող ենք օգտագործել «բացասական» ՝ որպես նշան ՝ նշելու ՝ զանգվածում տարր տեսե՞լ ենք, թե ոչ: Նկատի ունեցեք, որ մենք կարող ենք որոշ ցուցանիշներում պահված իրական արժեքը վերցնել ՝ օգտագործելով բացարձակ () գործառույթ, որը վերադարձնում է ամբողջ ամբողջության բացարձակ արժեքը: Այս եղանակով զանգվածը կարող է օգտագործվել և՛ որպես հեշ քարտեզ, և՛ որպես կոնտեյներ:

Օրինակ, եթե զանգվածում տեսել ենք «2» տարր, մենք կարող ենք նշանակել Array [1] = -1 * Array [1], որը մեզ կասի, որ զանգված 2-ում:

Այս հնարքը շահարկում է զանգվածը պահելու համար, եթե մենք ինդեքսի մեջ տարր ենք տեսել i, Ավարտելուց հետո մենք կարող ենք մի օղակ գործարկել [1, N] միջակայքում ՝ գտնելու համար բոլոր բացասական ամբողջ թվերը (նշանակում է, որ դրանք չեն տեսել) և, հետևաբար, տպել պահանջվող արդյունքը: Նկատենք, որ դա հնարավոր է միայն այն դեպքում, եթե մենք այդպիսին ենք Թույլատրվում զանգվածը փոխելու համար:

Ալգորիթմ

  1. Յուրաքանչյուր տարրի համար զանգվածում.
    • Եթե ​​Array [i - 1]> 0:
      • Սահմանեք սա որպես բացասական, կամ ՝ Array [i - 1] * = -1;
  2. Նախաձեռնեք ցուցակը / վեկտորը արդյունք բոլոր բացակայող տարրերը պահելու համար
  3. Յուրաքանչյուր ամբողջ թիվ [1, N] միջակայքում (N = զանգվածի չափը):
    • If Rayանգված [i]> 0
      • Ավելացրեք այս տարրը i դեպի արդյունք
  4. Վերադառնալ արդյունք
  5. Տպեք արդյունքը

Rayանգվածի 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

Rayանգվածի Leetcode լուծույթում անհետացած բոլոր թվերի բարդության վերլուծություն

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

ՎՐԱ) քանի որ մենք վազում ենք զանգվածի երկու անցում ՝ անկախ մուտքից, որպեսզի գտնենք բացակայող տարրերը: N = զանգվածի չափը:

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

Ո (1) քանի որ մենք օգտագործում ենք հիշողության անընդհատ տարածություն: