未排序数组中每个元素计数的累积频率


难度级别 易得奖学金
经常问 Cadence印度 狂徒 LinkedIn 月蛙实验室 Pinterest
排列 哈希 排序

我们得到了一个未排序的数组。 任务是计算未排序的每个元素的累计计数频率 排列.

使用案列

输入:

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个元素,则visit [i]为true,否则为false。
  2. 用0初始化一个变量sum,该变量sum将存储元素的累积频率。
  3. 对0到n-1的I进行循环
    • 如果访问的I为假,则将计数变量初始化为零,该变量将存储当前元素的计数
    • 对范围i到n-1中的j运行循环
      • 如果A [j]等于A [i],则将计数递增1,并将visited [j]标记为true
    • 将总数相加。
    • 打印总和。
  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的访问数组,因此空间复杂度为 上).

方法2:使用排序

大意

我们将首先对数组进行排序,然后计算每个元素的频率。

算法

  1. 声明一个将存储该计数的变量计数。
  2. 初始化一个变量count = 1,它将存储当前字符的计数。
  3. 声明一个变量n,该变量存储输入数组的大小。
  4. 对输入数组进行排序。
  5. 对1到n范围内的I进行循环
    • 如果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

未排序数组中每个元素计数的累积频率的复杂性分析

时间复杂度

由于我们仅对输入数组进行两次迭代,因此时间复杂度为 上).

空间复杂度

我们正在使用哈希表来存储元素的频率。 所以空间复杂度是 上).

參考資料