K-й виразний елемент у масиві


Рівень складності Medium
Часто запитують у саман Амазонка Apple ByteDance eBay Expedia Facebook Google LinkedIn Microsoft оракул Salesforce Spotify Лабораторії Walmart
Розділяй і володарюй купа

Вам дано ціле число масив A, надрукувати k-й окремий елемент у масиві. Даний масив може містити дублікати, і на виході повинен бути надрукований k-й виразний елемент серед усіх унікальних елементів масиву. Якщо k більше, ніж кількість різних елементів, повідомте про це.

Приклад

Вхідний сигнал:

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

K = 2

вихід:

K-й неповторюваний елемент дорівнює 2.

Пояснення:

Перший неповторюваний елемент - 1,

Другий неповторюваний елемент - 2.

Підхід 1: Груба сила

Головна думка

Ми будемо підтримувати змінну count, яка буде зберігати кількість неповторюваних елементів, які ми знайшли. Тепер ми будемо робити ітерацію по всіх елементах, і для кожного елемента ми будемо робити ітерацію по масиву, щоб перевірити, є це неповторюваний елемент чи ні, якщо він є, тоді ми збільшимо рахунок на 1. Елемент, для якого count рівний K, ми надрукуємо цей елемент.

Алгоритм K-го виразного елемента в масиві

  1. Ініціалізуйте значення змінної count нулем, який буде рахувати кількість різних елементів у масиві.
  2. Запустіть цикл для I в діапазоні від 0 до n-1
    1. Оголосіть прапорець з false, що є істинним, якщо A [i] є повторюваним елементом, і навпаки
    2. Запустіть цикл для j в діапазоні від 0 до n-1
      1. Якщо I не дорівнює j, а A [i] дорівнює A [j], призначте прапор = 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

Аналіз складності для K-го виразного елемента в масиві

Часова складність

Ми використовуємо дві вкладені петлі, обидві розміром N. Отже, загальна складність часу становить O (N ^ 2).

Космічна складність

Ми не використовуємо зайвий простір, тому космічна складність є O (1).

Підхід 2: Використання хешування

Головна думка

Ми будемо зберігати частоту кожного елемента масиву в хеш-таблиці. Тепер ми будемо підтримувати змінну count, яка буде зберігати кількість знайдених нами елементів, що не повторюються. Далі ми проведемо ітерацію по всіх елементах, і для кожного елемента ми перевіримо, чи є його частота більше 1 чи ні, якщо вона дорівнює 1, то збільшимо відлік на 1. Елемент, для якого підрахунок стає рівний K, ми надрукуємо цей елемент.

Алгоритм K-го виразного елемента в масиві

  1. Оголосіть хеш-таблицю, яка буде зберігати частоту кожного елемента масиву.
  2. Ініціалізуйте значення змінної count нулем, який буде рахувати кількість різних елементів у масиві.
  3. Запустіть цикл для I в діапазоні від 0 до n-1
    1. Якщо частота A [i] дорівнює 1, збільште рахунок на 1.
    2. Якщо рахунок дорівнює K, надрукуйте A [i].
  4. Повертати

Наприклад:

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

K = 2

Хеш-таблиця буде виглядати так,

K-й виразний елемент у масиві

Реалізація

Програма 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

Аналіз складності для K-го виразного елемента в масиві

Часова складність

Ми повторюємо масив лише двічі. Отже, загальна складність часу становить O (N).

Космічна складність

Ми підтримуємо хеш-таблицю для зберігання частоти елементів у масиві. Отже, космічна складність є O (N).

посилання