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

Question

给定一个包含重复项的整数排序数组。查找数组中存在的每个唯一元素的频率。
频率定义为数组中任何元素出现的次数。

例如 ：

Input:
int[] arr = {2, 2, 2, 3, 3, 4, 5, 5, 6, 6};
Output:
Frequency of 2 is : 3
Frequency of 3 is : 2
Frequency of 4 is : 1
Frequency of 5 is : 2
Frequency of 6 is : 2

Answer 1

我们首先讨论divide and conquer解决这个问题的基本策略。
每次调用我们的函数时，我们将数组分成两半，每次将我们的问题分成两半，导致最坏的时间复杂度为O(log(n))。

我们的数组实际上并没有被分成两半，但是我们保留了两个指针 start 和 end 代表要使用的数组的某个部分，这就是我们的数组实际上是如何拆分的。

我们知道我们的数组已经排序。所以我们可以得出结论，

• 如果开始指针和结束指针处的元素等于要计算频率的元素，这意味着整个虚拟数组仅包含该元素，因此我们直接添加(end-start+1)到我们的频率计数中。
• 如果不是这种情况，我们对数组的两半进行重复，并按后序将这两个结果的调用相加，以得出最终的频率计数结果。
  现在，整个算法用于查找数组中一个元素的频率。
  为了找到每个元素的频率，每次都需要调用这个函数。
  因此，使用该算法解决此问题的总体最坏时间复杂度为
  O(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 < 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.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 < 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