Verilmiş bir Tam Arrayın Bütün Fərqli Elementlərini Çap et

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon MakeMyTrip Zoho
Geyim Sükut çeşidləyiciBaxılıb 38

Tam bir sıra verildikdə, massivdəki bütün fərqli elementləri çap edin. Verilmişdir array dublikat ola bilər və nəticə hər elementi yalnız bir dəfə çap etməlidir. Verilən sıra sıralanmır.

misal

Input:

nums [] = {12, 10, 9, 45, 2, 10, 10, 45}

Çıxış:

12, 10, 9, 45, 2

Yanaşma 1: Kobud güc həlli

Əsas fikir

Hər bir element üçün dəyəri eyni olan və indiki indeksdən kiçik bir indeksə sahib başqa bir elementin olub olmadığını yoxlayın. Belə bir element yoxdursa, cari elementi çap edin, əks halda atlayın.

Alqoritm

  1. 0-dan n-1 aralığında I üçün bir döngə çalıştırın
    1. 0 - i aralığında j üçün bir döngə çalışdırın
      • J == I olarsa, ədədi [i] yazdırın.
      • Nums [i] nums [j] -ə bərabərdirsə, bu döngədən çıxın.
    2. Qayıt.

Verilmiş bir Tam Arrayın Bütün Fərqli Elementlərini Çap üçün İcra

C ++ proqramı

#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 proqramı

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

Verilmiş bir Tam Arrayın Bütün Fərqli Elementlərini Çap üçün Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Hər birinin ölçüsü n olan iki iç içə döngəmiz var. Yəni zamanın mürəkkəbliyi O (N ^ 2).

Kosmik Mürəkkəblik

Zamanın mürəkkəbliyi olduğu üçün əlavə bir yer istifadə etməmişik O (1).

Yanaşma 2: Hashing ilə optimallaşdırılmış həll

Əsas fikir

Artıq yazdırdığımız elementləri saxlayacaq bir hash masası saxlayacağıq. Beləliklə, massivi təkrarlayacağıq, əgər massivdə hash cədvəlində olmayan bir element tapsa, o elementi çap edəcəyik, sonra hash cədvəlinə daxil edəcəyik, əks halda həmin elementi atlayacağıq.

Alqoritm

  1. Bir hash cədvəli elan edin.
  2. 0-dan n-1 aralığında I üçün bir döngə işlədin:
    • Num [i] hash cədvəlində yoxdursa, onu çap edib hash cədvəlinə daxil edin.
    • Num [i] hash cədvəlində yoxdursa, onu atlayın.
  3. Qayıt.

Məsələn, deyək

saylar [] = {3, 3, 1, 2, 1}

Sol tərəfdəki cədvəl giriş dizimizdir və cari indeksə narıncı rəng göstərir.

Sağdakı cədvəl hash cədvəlidir.

Verilmiş bir Tam Arrayın Bütün Fərqli Elementlərini Çap etPin

Verilmiş bir Tam Arrayın Bütün Fərqli Elementlərini Çap üçün İcra

C ++ proqramı

#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 proqramı

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

Verilmiş bir Tam Arrayın Bütün Fərqli Elementlərini Çap üçün Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Massivi yalnız bir dəfə təkrarlayırıq və sıralanmamış çoxluqda insert funksiyasının zaman mürəkkəbliyi O (1), yəni ümumi zaman mürəkkəbliyi O (N).

Kosmik mürəkkəblik

Məkan mürəkkəbliyimiz olduğu üçün əlavə bir hash masası götürdük O (N).

References

Translate »