Дар ҳалли массиви Leetcode ҳама рақамҳои гумшударо ёбед  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon себ Блумберг Google Microsoft Yahoo
алгоритмҳо тартиботи ҳарбӣ рамзгузорӣ Хашм мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions

Изҳороти мушкилот  

Дар ин масъала, ба мо як асал ададҳо. Он унсурҳои аз 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 ба щайд
  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 нопадидшуда

Мураккабии вақт

О (Н) чунон ки мо тамоми массивро як маротиба тай карда, ададҳоро қайд мекунем. N = андозаи массив.

ҳамчунин нигаред
Муайян кардани ҳалли суроғаи IP-и Leetcode

Мураккабии фазо 

О (Н) вақте ки мо ҳамаи рақамҳои дар массив мавҷудбударо дар ҷадвали хэш нигоҳ медорем. Дар хотир доред, ки мо массиви баромади худро дар саҳмгузории мураккабии фазо баррасӣ намекунем.

Равиш (тағирот дар ҷои худ)  

Як нуктае, ки дар ин масъала бояд мушоҳида шавад, ин аст: "массив ҳамеша унсурҳои андозаи худро камтар ё баробар дорад". Ин маънои онро дорад, ки ҳамон қадар нишондиҳандаҳо ҳамон қадар унсурҳои гуногун мавҷуданд. Инчунин, унсурҳои гумшуда ҳамеша аз 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 ба натиҷа
  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 нопадидшуда

Мураккабии вақт

О (Н) вақте ки мо ду гузариши массивро сарфи назар аз вуруд барои ёфтани унсурҳои гумшуда иҷро мекунем. N = андозаи массив.

Мураккабии фазо 

О (1) вақте ки мо фазои хотираи доимиро истифода мебарем.

1