Першы не паўтаральны элемент


Узровень складанасці Лёгка
Часта пытаюцца ў Белзабар Комлі СМІ MetLife Snapdeal Спрынклер Вукер
масіў гашыш Пошук

Нам дадзены масіў А. Мы павінны знайсці першы ў масіве не паўтаральны элемент.

Прыклад

Уваход:

A [] = {2,1,2,1,3,4}

Вынахад:

Першы не паўтаральны элемент: 3

Паколькі 1, 2 не з'яўляецца адказам, таму што яны паўтараюцца, а 4 - не адказам, таму што нам трэба знайсці першы элемент, які не паўтараецца, а гэта 3, а не 4.

Падыход 1: Грубая сіла

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

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

Алгарытм

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

Рэалізацыя першага элемента, які не паўтараецца

Праграма C ++

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

Праграма JAVA

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

Аналіз складанасці першага не паўтаральнага элемента

Складанасць часу

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

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

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

Падыход 2: Выкарыстанне хэшавання

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

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

Алгарытм

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

Зразумейце на прыкладзе

A [] = {2, 1, 2, 1, 3, 4}

Тады хэш-табліца будзе выглядаць так:

Першы не паўтаральны элемент

Рэалізацыя першага элемента, які не паўтараецца

Праграма C ++

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            cout << "First non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

Праграма JAVA

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        for(int i=0;i<n;i++)
        {
            Integer freq = hash_table.get(A[i]);
            hash_table.put(A[i], (freq == null) ? 1 : freq + 1); 
        }

        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                System.out.println("First non-repeating element is: "+A[i]);
                return;
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

Аналіз складанасці першага не паўтаральнага элемента

Складанасць часу

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

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

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

Спасылкі