JavaScript 用于计算数组元素的频率

在本文中，我们给出一个可能包含重复值的数组。如果存在重复值，我们将打印出所有元素及其频率。我们可以通过使用两种方法来实现这一点：

使用两个循环
使用散列
使用二分查找函数

示例：

Input :  arr[] = {10, 20, 20, 10, 10, 20, 5, 20}  
Output : 10 3  
         20 4  
         5  1  

Input : arr[] = {10, 20, 20}  
Output : 10 1  
         20 2

简单的解决方案 就是运行两个循环。对于每个项，计算它出现的次数。为了避免重复打印，要跟踪处理过的项

示例1： 以下是上述方法的实现：

Javascript

<script>
    // JavaScript program to count frequencies of array items
 
    function countFreq(arr, n) {
        let visited = Array.from({ length: n }, (_, i) => false);
 
        // Traverse through array elements and
        // count frequencies
        for (let i = 0; i < n; i++) {
 
            // Skip this element if already processed
            if (visited[i] == true)
                continue;
 
            // Count frequency
            let count = 1;
            for (let j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) {
                    visited[j] = true;
                    count++;
                }
            }
            console.log(arr[i] + " " + count);
        }
    }
 
    // Driver Code
 
    let arr = [10, 20, 20, 10, 10, 20, 5, 20];
    let n = arr.length;
    countFreq(arr, n);
</script>

输出：

10 3  
20 4  
5 1

时间复杂度: O(n2), 其中n为每个循环的时间。

辅助空间: O(n), 用于保存visited数组。

示例2: 一种高效的解决方案是使用哈希表:

JavaScript

<script>
    function countFreq(arr, n) {
        var mp = new Map();
     
        // Traverse through array elements and
        // count frequencies
        for (var i = 0; i < n; i++) {
            if (mp.has(arr[i]))
                mp.set(arr[i], mp.get(arr[i]) + 1)
            else
                mp.set(arr[i], 1)
        }
     
        var keys = [];
        mp.forEach((value, key) => {
            keys.push(key);
        });
        keys.sort((a, b) => a - b);
     
        // Traverse through map and print frequency
        keys.forEach((key) => {
     
            console.log(key + " " + mp.get(key));
        });
    }
     
    var arr = [10, 20, 20, 10, 10, 20, 5, 20];
    var n = arr.length;
    countFreq(arr, n);
</script>

输出：

5 1  
10 3  
20 4

示例3： 在上述高效解决方案中，如何按输入中的顺序打印元素：

Javascript

<script>
    function countFreq(arr, n) {
        var mp = new Map();
     
        // Traverse through array elements and
        // count frequencies
        for (var i = 0; i < n; i++) {
            if (mp.has(arr[i]))
                mp.set(arr[i], mp.get(arr[i]) + 1)
            else
                mp.set(arr[i], 1)
        }
     
        // To print elements according to first
        // occurrence, traverse array one more time
        // print frequencies of elements and mark
        // frequencies as -1 so that same element
        // is not printed multiple times.
        for (var i = 0; i < n; i++) {
            if (mp.get(arr[i]) != -1) {
                console.log(arr[i] + " " + mp.get(arr[i]));
                mp.set(arr[i], -1);
            }
        }
    }
     
    var arr = [10, 20, 20, 10, 10, 20, 5, 20];
    var n = arr.length;
    countFreq(arr, n);
</script>

输出：

10 3  
20 4  
5 1

另一种高效的解决方案（空间优化）： 我们可以使用二分搜索函数来找到数组元素的频率。首先，我们将对数组进行排序以进行二分搜索。数组中元素的频率将是数组中某个元素的最后一次出现和第一次出现的差加一。

示例：

Javascript

//Function to find frequency of elements in the array
function countFreq(arr, n) {
    arr.sort((a, b) => a - b); //sort array for binary search
    let i = 0;
    while (i < n) {
        //index of first and last occ of arr[i]
        const first_index = arr.indexOf(arr[i]);
        const last_index = arr.lastIndexOf(arr[i]);
        i = last_index;
 
        const fre = last_index - first_index + 1; //finding frequency
        console.log(arr[i] + " " + fre); //printing frequency
        i++;
    }
}
 
// Driver code
const arr = [10, 20, 20, 10, 10, 20, 5, 20];
countFreq(arr, arr.length);

输出