Эрэмбэлэгдээгүй массив дахь элемент бүрийн тоолох хуримтлагдсан давтамж


Хэцүү байдлын түвшин Easy
Байнга асуудаг Cadence Энэтхэг Фанатикууд LinkedIn Moonfrog лабораторууд Pinterest
Array Хаш Ангилах

Бидэнд ангилаагүй массив өгсөн. Даалгавар бол элемент бүрийн тоолох хуримтлагдсан давтамжийг ангилагдаагүй байдлаар тооцоолох явдал юм массив.

Гарчиг

Жишээ нь

Орц:

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. Оруулсан массивын ижил хэмжээтэй зочилсон массивыг зарлана уу, хэрэв хариуд нь ith элемент оруулсан бол зочилсон [i] үнэн, өөрөөр хэлбэл худал байна.
  2. Элементүүдийн хуримтлагдсан давтамжийг хадгалах хувьсагчийн нийлбэрийг 0-ээр эхлүүлнэ.
  3. 0-ээс n-1 хүртэлх мужид зориулж гогцоо ажиллуулна уу
    • Хэрэв I-д зочилсон бол худал утгатай бол тоолох хувьсагчийг тэгээр эхлүүлээрэй
    • I-ээс n-1 хүртэлх мужид j давталтыг ажиллуулна
      • Хэрэв 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. 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. 0-ээс n-1 хүртэлх мужид i давталтыг ажиллуулна уу
    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).

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