在本教程中，我们将看到如何在排序阵列中计算每个元素的出现数(或者频率)

问题

给定包含重复项的整数阵列。
找到阵列中存在的每个唯一元素的频率。
频率被定义为阵列中任何元素的发生次数。

例如 ：

输入：int [] arr = {2,2,2,3,3,4,5,5,6,6};

输出：2的频率为：3频率为：2频率为4是：1频率为5是：2频率为6是：2

解决方案

让我们先讨论基本 divide and conquer解决这个问题的策略。
我们每次将阵列划分为两半，每次都被称为将问题分成一半，每次都会产生最糟糕的时间复杂 O(log(n))。

我们的阵列实际上并不实际分为一半，但我们保留两个指针开始和结束代表某些部分的数组与之合作，这就是我们的数组几乎拆分的方式。

我们知道我们的阵列已被排序。
所以我们可以得出结论，

• 如果启动指针和终点指针处的元素等于要计算频率的元素，则这意味着整个虚拟阵列仅包含该元素，因此我们直接添加 (end-start+1)我们的频率计数。
• 如果不是这种情况，我们会重复阵列的两半，并在邮政订单中，我们将添加这两个结果的呼叫，以使我们的最终频率计数结果。

现在，这整个算法用于查找阵列中的一个元素的频率。
用于查找每个元素的频率，每次都需要调用此函数。
因此，通过这种算法解决这个问题的总体糟糕时间复杂性将是

O(n*log(n))。

package org.arpit.theitroad;
 
import java.util.HashSet;
import java.util.Scanner;
 
public class FreqOfEachElems {
 
	public static void main(String[] args) {
 
		Scanner scn = new Scanner(System.in);
		int[] arr = new int[scn.nextInt()];
 
		for (int i = 0; i < arr.length; i++) {
			arr[i] = scn.nextInt();
		}
 
		HashSet<Integer> processed = new HashSet();
		for (int val : arr) {
			if (!processed.contains(val)) {
				System.out.println("Frequency of " + val + " is : " + 
						solveRecursive(0, arr.length - 1, arr, val));
				processed.add(val);
			}
		}
 
	}
 
	public static int solveRecursive(int start, int end, int[] arr, int element) {
		/* if start is greater than n, we need to return because this 
          represent a subarray of negative size.*/
		if (start > end) {
			return 0;
		}
 
		/* this means that the size of the virtual subarray is one, 
		 * and it has only single element. */
		if (start == end) {
			/* now if this single element is equal to the element 
			 * whose frequency we are finding out, 
			 * then it will contribute one for its total frequency 
			 * in the whole array. */
			if (arr[start] == element && arr[end] == element) {
				return 1;
			} else {
				return 0;
			}
		}
 
		/* if the virtual subarray is of size greater than one, 
		 * and the elements at start and at the end are equal, 
		 * this means that whole array consists of 
		 * that element only, as the array 
		 * we are working on is already sorted.*/
		if (arr[start] == element && arr[end] == element) {
			return (end - start + 1);
		}
 
		int mid = (start + end)/2;
		/* call for left side virtual subarray */
		int leftResult = solveRecursive(start, mid, arr, element);
 
		/* call for right side virtual subarray.*/
		int rightResult = solveRecursive(mid + 1, end, arr, element);
 
		/* our result will be calculated in postorder, 
		 * which will be left side result 
		 * plus the right side sum.*/
		return leftResult + rightResult;
	}
}

有效的方法：

还有一种迭代且甚至有效的方法，也可以在线性时间解决单个解析中的问题： O(n)。

我们可以做的是，我们通过阵列保持频率阵列和循环，每次找到任何元素我们都会进入频率阵列，并在频率阵列中添加1到上一个元素的频率。
循环结束后，我们留下了阵列，其中每个索引在原始阵列中的频率处于原始阵列。
也是最大的加点以及其效率，我们不一定需要排序阵列。

例如：考虑阵列及其频率阵列， int[] arr = {5,4,3,2,4,3,2,5,5};int[] freqArr = {0,0,0,0,0,0};循环结束后的频率阵列看起来像， int[] freqArr = {0,0,2,2,1,3};

在此频率阵列中，每次 i索引，频率 i在实际阵列中坐着。

到这时，我们已经知道这种方法的缺点，是的，当输入阵列包含大于10 ^ 9的数字时，这种方法不会有效。
因为我们没有任何负面指数，并且不可能阵列10 ^ 9.
因此，为了处理，我们需要使用我们存储的HashMap

element-frequency将作为HashMap中的键值对配对。

package org.arpit.theitroad;
 
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
 
public class FreqOfEachElems {
 
	public static void main(String[] args) {
 
		Scanner scn = new Scanner(System.in);
		int[] arr = new int[scn.nextInt()];
 
		for (int i = 0; i < arr.length; i++) {
			arr[i] = scn.nextInt();
		}
 
		System.out.print("arr[]: {");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(" "+arr[i]);
		}
 
		System.out.println(" }");
		HashMap<Integer, Integer> freqMap = solveIterative(arr);
 
		for(int val : freqMap.keySet())
		{
			System.out.println("Frequency of " + val + " is : " + freqMap.get(val));
		}
 
	}
 
	public static HashMap<Integer, Integer> solveIterative(int[] arr)
	{
		HashMap<Integer,	Integer> freqMap = new HashMap<>();
 
		/* iterate through the array for contributing +1 
		 * as a frequency of that element, every time it is encountered.*/
		for(int val : arr)
		{
			if(!freqMap.containsKey(val))
			{
				/* if hashmap doesnt contains that element, 
				 * this means this is the first time the element is encountered,
				 * therefor freq of this element will be one for now.*/
				freqMap.put(val, 1);
			}
			else {
				/* if hashmap contains this element, 
				 * so now its updated frequency will be its past frequency + 1.
				 */
				freqMap.put(val, freqMap.get(val)+1);
			}
		}	
		return freqMap;
	}
}

运行上面的程序时，我们将得到以下输出

8
4 3 2 2 3 4 4 5
arr[]: { 4 3 2 2 3 4 4 5 }
Frequency of 2 is : 2
Frequency of 3 is : 2
Frequency of 4 is : 3
Frequency of 5 is : 1