This approach involves using a HashMap (or dictionary in Python) to count the occurrences of each element in the array. This will help in efficiently checking if an element exists and how many times it appears, which is useful for problems requiring frequency analysis.
Time Complexity: O(n), as it iterates over the array once. Space Complexity: O(1) if the element range is known and constant, or O(k) where k is the range of elements.
1import java.util.HashMap;
2
3public class ElementCounter {
4 public static void countElements(int[] arr) {
5 HashMap<Integer, Integer> frequency = new HashMap<>();
6 for (int num : arr) {
7 frequency.put(num, frequency.getOrDefault(num, 0) + 1);
8 }
9 for (var entry : frequency.entrySet()) {
10 System.out.println("Element " + entry.getKey() + " appears " + entry.getValue() + " times");
11 }
12 }
13
14 public static void main(String[] args) {
15 int[] arr = {1, 3, 1, 2, 3, 4, 5, 3};
16 countElements(arr);
17 }
18}In Java, a HashMap is used, which efficiently handles the counting of each element's frequency. The getOrDefault method simplifies handling new and existing keys in the map.
Another approach is sorting the array and then identifying repeated elements by comparison with neighboring elements. This leverages the efficiency of modern sorting algorithms to bring repeated elements together, making it trivial to count consecutive duplicates.
Time Complexity: O(n log n) due to the sort operation. Space Complexity: O(1) if in-place sorting is considered.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 return (*(int*)a - *(int*)b);
6}
7
8void countSortedElements(int arr[], int size) {
9 qsort(arr, size, sizeof(int), compare);
10 int count = 1;
11 for (int i = 1; i < size; i++) {
12 if (arr[i] == arr[i - 1]) {
13 count++;
14 } else {
15 printf("Element %d appears %d times\n", arr[i - 1], count);
16 count = 1;
17 }
18 }
19 printf("Element %d appears %d times\n", arr[size - 1], count);
20}
21
22int main() {
23 int arr[] = {1, 3, 1, 2, 3, 4, 5, 3};
24 int size = sizeof(arr) / sizeof(arr[0]);
25 countSortedElements(arr, size);
26 return 0;
27}This C solution sorts the input array using quicksort and then counts consecutive elements to tally occurrences. Sorting ensures similar elements cluster together, thus simplifying frequency determination.