Массив дахь ялгаатай элемент


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн БайтДанс Ebay Expedia Facebook-ийн Google-ийн LinkedIn Microsoft- Oracle-ийн Борлуулалтын хүч Spotify Walmart лабораторууд
Хуваагаад, ялж байна Нуруулаг

Танд бүхэл тоо өгнө массив A, массив дахь k-р ялгаатай элементийг хэвлэ. Өгөгдсөн массив нь давхардсан байж болох бөгөөд гаралт нь массив дахь бүх өвөрмөц элементүүдийн дунд k-р ялгаатай элементийг хэвлэх ёстой. Хэрэв k нь хэд хэдэн ялгаатай элементээс их байвал түүнийгээ мэдээлнэ үү.

Жишээ нь

Орц:

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

K = 2

Үр дүн:

K-р давтагдаагүй элемент нь 2 байна.

Тайлбар:

Эхний давталтгүй элемент нь 1,

Хоёр дахь давтагдаагүй элемент нь 2 юм.

Хандлага 1: Харгис хүч

Үндсэн санаа

Бид олсон давтагдахгүй элементүүдийн тоог хадгалах тооллын хувьсагчийг хадгалах болно. Одоо бид бүх элементүүдийг давтаж, элемент бүрийн хувьд массивыг давтаж, энэ нь давтагдаагүй элемент мөн эсэхийг шалгана, хэрэв тийм бол тооллыг 1-ээр нэмэгдүүлнэ. K-тэй тэнцүү бол бид тухайн элементийг хэвлэх болно.

Массив дахь ялгаатай элементийн алгоритм

  1. Массив дахь ялгаатай элементүүдийн тоог тоолох хувьсах тооллыг тэгээр эхлүүлнэ.
  2. 0-ээс n-1 хүртэлх мужид зориулж гогцоо ажиллуулна уу
    1. Хэрэв A [i] нь давтагдах элемент бөгөөд эсрэгээр байвал хуурамч тугийг зарлана уу
    2. 0-ээс n-1 хүртэлх j-ийн давталтыг ажиллуулна уу
      1. Хэрэв би j-тэй тэнцэхгүй бол A [i] нь A [j] -тэй тэнцүү бол flag = true-ийг өгөөд завсарла
    3. Хэрэв туг хуурамч байвал 1-ээр нэмэгдүүлнэ
    4. Шалгах Хэрэв тоо нь K-тэй тэнцүү бол A [i] -г хэвлэ.
  3. буцах

Хэрэгжүүлэх

C ++ програм

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        bool flag = false;
        for (int j = 0; j < n; j++)
        {
            if (i != j and A[i] == A[j])
            {
                flag = true;
                break;
            }
        }
        if (!flag)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA хөтөлбөр

public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            boolean flag = false;
            for (int j = 0; j < n; j++)
            {
                if (i != j && A[i] == A[j])
                {
                    flag = true;
                    break;
                }
            }
            if (!flag)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

Массив дахь ялгаатай элементийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Бид хоёулаа N хэмжээтэй, үүрлэсэн хоёр гогцоог ашиглаж байна. Тэгэхээр нийт хугацааны нарийн төвөгтэй байдал нь ийм байна O (N ^ 2).

Сансрын нарийн төвөгтэй байдал

Бид нэмэлт зай ашиглахгүй байгаа тул орон зайн нарийн төвөгтэй байдал ийм байна O (1).

Хандалт 2: Хэш ашиглах

Үндсэн санаа

Бид массивын элемент бүрийн давтамжийг хэш хүснэгтэд хадгалах болно. Одоо бид олсон давтагдахгүй элементүүдийн тоог хадгалах тооллын хувьсагчийг хадгалах болно. Дараа нь бид бүх элементүүдийг давтаж, элемент бүрийн хувьд давтамж нь 1-ээс их байгаа эсэхийг эсвэл 1-тэй тэнцүү эсэхийг шалгаж, тооллыг 1-ээр нэмэгдүүлнэ. K-тэй тэнцүү бол бид тухайн элементийг хэвлэх болно.

Массив дахь ялгаатай элементийн алгоритм

  1. Массивын элемент бүрийн давтамжийг хадгалах хэш хүснэгтийг зарлана уу.
  2. Массив дахь ялгаатай элементүүдийн тоог тоолох хувьсах тооллыг тэгээр эхлүүлнэ.
  3. 0-ээс n-1 хүртэлх мужид зориулж гогцоо ажиллуулна уу
    1. Хэрэв A [i] -ийн давтамж 1 бол 1-ээр нэмэгдүүлнэ.
    2. Хэрэв тоо нь K-тэй тэнцүү бол A [i] гэж хэвлэ.
  4. буцах

Жишээлбэл:

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

K = 2

Хэш хүснэгт иймэрхүү харагдах болно,

Массив дахь ялгаатай элемент

Хэрэгжүүлэх

C ++ програм

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    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)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA хөтөлбөр

import java.util.*; 
public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        HashMap <Integer, Integer> hash_table = new HashMap<Integer, Integer> ();  
        for (int i = 0; i < n; i++)  
        { 
            if(hash_table.containsKey(A[i])) 
                hash_table.put(A[i], hash_table.get(A[i]) + 1); 
            else
                hash_table.put(A[i], 1); 
        } 
        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

Массив дахь ялгаатай элементийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Бид массив дөнгөж хоёр удаа давтаж байна. Тэгэхээр нийт цаг хугацааны нарийн төвөгтэй байдал нь O (N).

Сансрын нарийн төвөгтэй байдал

Массив дахь элементүүдийн давтамжийг хадгалах хэш хүснэгтийг хадгалж байна. Тиймээс, сансрын нарийн төвөгтэй байдал нь юм O (N).

Ашигласан материал