Надрукаваць усе асобныя элементы дадзенага цэлага масіва


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка MakeMyTrip Zoho
масіў гашыш сартаванне

Улічваючы цэлы масіў, раздрукуйце ўсе розныя элементы ў масіве. Дадзенае масіў можа ўтрымліваць дублікаты, і вывад павінен друкаваць кожны элемент толькі адзін раз. Дадзены масіў не сартуецца.

Прыклад

Уваход:

нумары [] = {12, 10, 9, 45, 2, 10, 10, 45}

Вынахад:

12, 10, 9, 45, 2

Падыход 1: Рашэнне грубай сілы

Галоўная ідэя

Для кожнага элемента праверце, ці прысутнічае іншы элемент, значэнне якога аднолькавае і мае індэкс менш, чым бягучы індэкс. Калі такога элемента няма, раздрукуйце бягучы элемент, інакш прапусціце яго.

Алгарытм

  1. Запусціце цыкл для I у дыяпазоне ад 0 да n-1
    1. Запусціце цыкл для j у дыяпазоне ад 0 да i
      • Калі j == I, надрукуйце нумары [i].
      • Калі nums [i] роўна nums [j], выбярыце з гэтага цыкла.
    2. Вяртанне.

Рэалізацыя для друку ўсіх асобных элементаў дадзенага цэлага масіва

Праграма C ++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==i)
            {
                cout<<nums[j]<<" ";
            }
            if(nums[i]==nums[j])
            {
                break;
            }
        }
    }
    return 0;
}
5
3 3 1 2 1
3 1 2

Праграма JAVA

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
        {
            nums[i] = sc.nextInt();;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j==i)
                {
                    System.out.print(nums[i]+" ");
                }
                if(nums[i]==nums[j])
                {
                    break;
                }
            }
        }
  }
}

10 
4 6 6 2 6 3 4 2 2 7
4 6 2 3 7

Аналіз складанасці для друку ўсіх асобных элементаў дадзенага цэлага масіва

Часовая складанасць

У нас ёсць дзве ўкладзеныя завесы, кожная памерам n. Такім чынам, складанасць часу O (N ^ 2).

Касмічная складанасць

Мы не выкарыстоўвалі лішняга месца, таму складанасць часу складаная O (1).

Падыход 2: Аптымізаванае рашэнне з хэшаваннем

Галоўная ідэя

Мы будзем весці хэш-табліцу, у якой будуць захоўвацца элементы, якія мы ўжо надрукавалі. Такім чынам, мы будзем рабіць ітэрацыю масіва, калі знойдзены элемент у масіве, якога няма ў хэш-табліцы, мы надрукуем гэты элемент, а потым увядзём яго ў хэш-табліцу, інакш гэты элемент пропусцім.

Алгарытм

  1. Абвясціце хэш-табліцу.
  2. Запусціце цыкл для I у дыяпазоне ад 0 да n-1:
    • Калі nums [i] адсутнічае ў хэш-табліцы, раздрукуйце яго і ўстаўце ў хэш-табліцу.
    • Калі nums [i] адсутнічае ў хэш-табліцы, прапусціце яго.
  3. Вяртанне.

Напрыклад, скажам

нумары [] = {3, 3, 1, 2, 1}

Табліца злева - гэта наш уваходны масіў і аранжавы колер паказвае на бягучы індэкс.

Табліца справа - хэш-табліца.

Надрукаваць усе асобныя элементы дадзенага цэлага масіва

Рэалізацыя для друку ўсіх асобных элементаў дадзенага цэлага масіва

Праграма C ++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    unordered_set<int> hash_table;
    for(int i=0;i<n;i++)
    {
        if(hash_table.count(nums[i])==0)  //hash_table.count(x) returns 1 if x is present in the hash_table otherwise returns 0
        {
            hash_table.insert(nums[i]);
            cout<<nums[i]<<" ";
        }
    }
    return 0;
}
5
3 3 1 2 1
3 1 2

Праграма JAVA

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
        {
            nums[i] = sc.nextInt();;
        }
        Set<Integer> hash_table = new HashSet<Integer>(); 
        for(int i=0;i<n;i++)
        {
            if(!hash_table.contains(nums[i]))  
            {
                hash_table.add(nums[i]);
                System.out.print(nums[i]+" ");
            }
        }
  }
}

10 
1 2 2 1 3 5 6 3 4 9
1 2 3 5 6 4 9

Аналіз складанасці для друку ўсіх асобных элементаў дадзенага цэлага масіва

Часовая складанасць

Мы паўтараем масіў толькі адзін раз, і складанасць часу функцыі ўстаўкі ў неўпарадкаваным наборы роўная O (1), таму агульная складанасць часу роўная O (N).

Касмічная складанасць

Мы ўзялі дадатковую хэш-табліцу, каб наша касмічная складанасць была O (N).

Спасылкі