Sponsored
Sponsored
This approach uses a hash map (or dictionary) to count occurrences of elements in the data. By iterating through the data once to populate the hash map, we can achieve efficient lookups. The main idea is to traverse the input list, counting occurrences of each element, and storing these counts in a hash map for quick access in the future.
Time Complexity: O(n) for traversing the list once.
Space Complexity: O(k), where k is the range of input values (determined by MAX).
1import java.util.HashMap;
2import java.util.Scanner;
3
4public class ElementCounter {
5 public static void main(String[] args) {
6 Scanner scanner = new Scanner(System.in);
7 HashMap<Integer, Integer> count = new HashMap<>();
8 System.out.print("Enter number of elements: ");
9 int n = scanner.nextInt();
10 System.out.println("Enter the elements:");
11
12 for (int i = 0; i < n; ++i) {
13 int x = scanner.nextInt();
14 count.put(x, count.getOrDefault(x, 0) + 1);
15 }
16
17 // Example query
18 System.out.print("Enter element to query: ");
19 int query = scanner.nextInt();
20 System.out.println("Element " + query + " appears " + count.getOrDefault(query, 0) + " times");
21 }
22}This Java program uses a HashMap to maintain a count of each integer. It reads elements from input, updates the map accordingly, and allows querying the count of any element efficiently.
By sorting the input list, elements of the same value will be grouped together. We can then iterate through the sorted list to count the occurrences of each element. This takes advantage of the property of sorting to simplify the counting process.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional space for counting.
1using System.Linq;
class SortedElementCounter {
static void Main() {
Console.Write("Enter number of elements: ");
int n = int.Parse(Console.ReadLine());
int[] arr = new int[n];
Console.WriteLine("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = int.Parse(Console.ReadLine());
}
Array.Sort(arr);
Console.WriteLine("Sorted elements for counting:");
int current = arr[0];
int count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == current) {
count++;
} else {
Console.WriteLine($"Element {current} appears {count} times");
current = arr[i];
count = 1;
}
}
Console.WriteLine($"Element {current} appears {count} times");
}
}Utilizing C#'s Array.Sort(), this program enables efficient sorting and counting by traversing the sorted list once.