Кумулятивна частота підрахунку кожного елемента в несортованому масиві


Рівень складності Легко
Часто запитують у Каденс Індія Фанатики LinkedIn Moonfrog Labs Пінтерест
масив Мішанина Сортування

Нам дається несортований масив. Завдання полягає в обчисленні кумулятивної частоти підрахунку кожного елемента в невідсортованому масив.

Приклад

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

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

вихід:

Cumulative frequency of 2 in the array is: 3
Cumulative frequency of 3 in the array is: 5
Cumulative frequency of 4 in the array is: 7

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

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

Для кожного елемента масиву повторіть весь масив і підрахуйте частоту цього елемента. Також підтримуйте відвіданий масив, який буде зберігати елементи, які ми вже надрукували.

Алгоритм

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

Впровадження для сукупної частоти підрахунку кожного елемента

Програма C ++

#include <bits/stdc++.h>
using namespace std;
void freq_of_elements(vector<int> A)
{
    int n = A.size();
    vector<bool> visited(n, false);
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == false)
        {
            int count = 0;
            for (int j = i; j < n; j++)
            {
                if (A[i] == A[j])
                {
                    count++;
                    visited[j] = true;
                }
            }
            sum += count;
            cout << "Cumulative frequency of " << A[i] << " in the array is: " << sum << endl;
        }
    }
    return;
}
int main()
{
    vector<int> A = {2, 4, 3, 2, 2, 3, 4};
    freq_of_elements(A);
    return 0;
}
Cumulative frequency of 2 in the array is: 3
Cumulative frequency of 4 in the array is: 5
Cumulative frequency of 3 in the array is: 7

Програма JAVA

public class Main
{
    static void freq_of_elements(int A[])
    {
        int n = A.length;
        int sum=0;
        boolean visited[]= new boolean[n];
        for (int i = 0; i < n; i++)
        {
            if (visited[i] == false)
            {
                int count = 0;
                for (int j = i; j < n; j++)
                {
                    if (A[i] == A[j])
                    {
                        count++;
                        visited[j] = true;
                    }
                }
                sum+=count;
                System.out.println("Cumulative frequency of " + A[i] + " in the array is: " + sum);
            }
        }
    }
  public static void main(String[] args) {
    int A[]= {2, 4, 3, 2, 2, 3, 4};
    freq_of_elements(A);
  }
}
Cumulative frequency of 2 in the array is: 3
Cumulative frequency of 4 in the array is: 5
Cumulative frequency of 3 in the array is: 7

Аналіз складності для кумулятивної частоти підрахунку кожного елемента

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

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

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

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

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

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

Спочатку ми відсортуємо масив, а потім підрахуємо частоту кожного елемента.

Алгоритм

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

Впровадження для сукупної частоти підрахунку кожного елемента

Програма C ++

#include <bits/stdc++.h>
using namespace std;
void freq_of_elements(vector<int> A)
{
    sort(A.begin(), A.end());
    int n = A.size();
    int count = 1;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i == n or A[i] != A[i - 1])
        {
            sum += count;
            cout << "Cumulative frequency of " << A[i - 1] << " in the array is: " << sum << endl;
            count = 1;
        }
        else
        {
            count++;
        }
    }
    return;
}
int main()
{
    vector<int> A = {2, 4, 3, 2, 2, 3, 4};
    freq_of_elements(A);
    return 0;
}
Cumulative frequency of 2 in the array is: 3
Cumulative frequency of 3 in the array is: 5
Cumulative frequency of 4 in the array is: 7

Програма JAVA

import java.util.Arrays;
public class Main
{
    static void freq_of_elements(int A[])
    {
        Arrays.sort(A);
        int n = A.length;
        int sum=0;
        int count=1;
        for (int i = 1; i <= n; i++)
        {
            if (i == n || A[i] != A[i - 1])
            {
                sum+=count;
                System.out.println("Cumulative frequency of " + A[i-1] + " in the array is: " + sum);
                count=1;
            }
            else{
                count++;
            }
        }
    }
  public static void main(String[] args) {
    int A[]= {2, 4, 3, 2, 2, 3, 4};
    freq_of_elements(A);
  }
}
Cumulative frequency of 2 in the array is: 3
Cumulative frequency of 3 in the array is: 5
Cumulative frequency of 4 in the array is: 7

Аналіз складності для кумулятивної частоти підрахунку кожного елемента

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

Сортування масиву займає час O (N * logN), і після цього ми обходимо масив один раз. Отже, загальна складність часу дорівнює O (N * logN + N), що збігається з O (N * logN).

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

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

Примітка: Що робити, якщо нам потрібні частоти елементів відповідно до порядку першого входження?

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

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

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

Алгоритм

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

Приклад

Вхідний масив:

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

Після ітерації вхідного масиву хеш-таблиця буде виглядати так:

Кумулятивна частота підрахунку кожного елемента в несортованому масиві

Впровадження для сукупної частоти підрахунку кожного елемента

Програма C ++

#include <bits/stdc++.h>
using namespace std;
void freq_of_elements(vector<int> A)
{
    int n = A.size();
    int sum = 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]])
        {
            sum += hash_table[A[i]];
            cout << "Cumulative frequency of " << A[i] << " in the array is: " << sum << endl;
            hash_table[A[i]] = 0;
        }
    }
    return;
}
int main()
{
    vector<int> A = {2, 4, 3, 2, 2, 3, 4};
    freq_of_elements(A);
    return 0;
}
Cumulative frequency of 2 in the array is: 3
Cumulative frequency of 4 in the array is: 5
Cumulative frequency of 3 in the array is: 7

Програма JAVA

import java.util.Arrays;
public class Main
{
    static void freq_of_elements(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        int sum=0;
        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])!=0)
            {
                sum+=hash_table.get(A[i]);
                System.out.println("Cumulative frequency of " + A[i] + " in the array is: " + sum);
                hash_table.put(A[i], 0);
            }
        }
    }
  public static void main(String[] args) {
    int A[]= {2, 4, 3, 2, 2, 3, 4};
    freq_of_elements(A);
  }
}
Cumulative frequency of 2 in the array is: 3
Cumulative frequency of 4 in the array is: 5
Cumulative frequency of 3 in the array is: 7

Аналіз складності для кумулятивної частоти підрахунку кожного елемента в несортованому масиві

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

Оскільки ми робимо ітерацію над вхідним масивом лише двічі, то складність часу становить O (N).

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

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

посилання