计算排序数组中每个元素的出现次数（或频率）

皆是虚妄

给出一个包含重复项的整数排序数组。找出数组中每个元素的频率。
频率定义为数组中任何元素的次数。
例如 ：
Input:int[] arr = ；Output:Frequency of 2 is : 3Frequency of 3 is : 2Frequency of 4 is : 1Frequency of 5 is : 2Frequency of 6 is :2               
! h/ V; E9 @: L    解决方案:                                                               
# L( G- Q( g$ T6 y, Z7 M6 C                                                                我们先讨论一下divide and conquer解决这个问题的基本策略。
; K1 j; J1 `0 \5 D" ?4 {, m' @1 l$ W每次我们调用函数时，我们将数组分成两半，每次将我们的问题分成两半，导致最坏的时间复杂O(log(n))。
) r! q; X0 T+ l! j6 o& ^, J3 X我们的数组实际上没有分成两半，但我们保留了两个指针 start 和 end 代表要使用的数组的某个部分，这就是我们的数组实际上是如何拆分的。
我们知道我们的数组已经排名了。因此，我们可以得出结论，
/ k  R$ J% M( O2 [, u" d如果开始指针和结束指针处的元素等于要计算频率的元素，这意味着整个虚拟数组仅包含该元素，因此我们直接添加(end-start 1)在我们的频率计数中。
8 {% @+ f# {- C) t  r9 O2 D. `) t如果没有这种情况，我们将重复数组的两半，并按顺序调用这两个结果，以获得最终的频率计数结果。
! ^+ H# e% F4 b目前，整个算法用于搜索数组中元素的频率。
每次都需要调用此函数才能找到每个元素的频率。
$ W0 v7 V# ?  K因此，使用该算法解决这个问题的总体最坏时间复杂性是
/ k9 e( a, l+ s5 c* sO(n*log(n))。package org.arpit.java2blog;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  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)  * 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。
9 o+ y% e  E' w循环结束后，我们留下一个数组，它们的频率存在于原始数组的每个索引中。
4 ?, @( t" M9 z0 E而且有效的优点是，我们不一定需要对数组进行排序。
0 V6 @& {8 G7 T5 [' G! |4 H3 ~例如：
/ E# ]0 ~8 t9 y: y% B+ V考虑数组及其频率数组，
& h: s: H0 J- Q: O, ]0 u) A4 ~% v; ]int[] arr = ；int[] freqArr = ；循环后的频率数组看起来像，
int[] freqArr = ；在这个频率数组中，在每个频率数组中i 索引处，i  位于实际数组中。
! n& h5 ~- H6 V# v0 D- u( s& V这时，我们已经知道了这种方法的缺点，
是的，当输入数组包含负数或大于10时^这种方法不会有效。
因为我们没有负索引，而且大小是 10^9 数组是不可能的。
) T- k% y0 ^& O因此，我们需要使用它来解决这个问题Hashmap，我们将这element-frequency作为键值对存储 hashmap 中。
1 B, t) e6 h4 w4 F$ V2 ?package org.arpit.java2blog;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
0 F5 h4 W# f; G2 j+ X6 R- E; J84 3 2 2 3 4 4 5arr[]Frequency of 2 is : 2Frequency of 3 is : 2Frequency of 4 is : 3Frequency of 5 is :1