Finding Duplicates in a C# Array and Counting Occurrences: A Solution Without LINQ

Problem Analysis and Limitations of the Original Code

In C# programming, handling duplicate elements in an array is a common task. The original code attempts to count duplicates using nested loops but suffers from several key issues. First, the inner loop for (int j = i; j < array.Length - 1; j++) only compares adjacent elements, failing to detect non-adjacent duplicates. For example, in the array {10, 5, 10, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 11, 12, 12}, the first 10 and third 10 are not recognized as duplicates because they are not adjacent in the array. Second, the count variable count is not reset after each outer loop iteration, leading to cumulative errors. Furthermore, the output statement Console.WriteLine("\t\n " + array[i] + "occurse" + count) contains typos and formatting issues, reducing readability. These flaws prevent the original code from accurately completing the task of counting duplicate elements.

Optimized Solution: Using Dictionary<int, int> for Efficient Counting

To address these problems, we can employ the Dictionary<int, int> data structure to store each element and its occurrence count. The core idea is to leverage the key-value pair nature of dictionaries, where keys represent array elements and values represent their frequencies. Here is a detailed analysis of the implementation steps:

1. Initialize an empty dictionary: var dict = new Dictionary<int, int>().
2. Traverse each element in the array: Use a foreach loop to iterate over the array.
3. For each element value, use the dict.TryGetValue(value, out int count) method to attempt to retrieve its current count. If the key does not exist, count is initialized to 0.
4. Update the dictionary: Set dict[value] to count + 1, incrementing the occurrence count for that element.
5. After traversal, the dictionary contains all unique elements and their corresponding occurrence counts.
6. Finally, use another foreach loop to iterate over the dictionary and output each key-value pair, formatted as Console.WriteLine("Value {0} occurred {1} times.", pair.Key, pair.Value).

Example code implementation:

static void Main(string[] args)
{              
    int[] array = { 10, 5, 10, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 11, 12, 12 };
    var dict = new Dictionary<int, int>();
    
    foreach(var value in array)
    {
        dict.TryGetValue(value, out int count);
        dict[value] = count + 1;
    }
    
    foreach(var pair in dict)
        Console.WriteLine("Value {0} occurred {1} times.", pair.Key, pair.Value);
    Console.ReadKey();
}

This method has a time complexity of O(n), where n is the length of the array, as each element is processed only once. The space complexity is O(k), where k is the number of unique elements in the array, and in the worst case (all elements are unique), it is O(n). Compared to the original code's O(n²) time complexity, this approach significantly improves efficiency.

Supplementary Reference: Brief Comparison with LINQ Methods

While this article focuses on solutions without LINQ, as a supplement, LINQ offers a more concise way to handle duplicate element counting. For example, using the GroupBy operator groups array elements and then counts each group. Example code:

int[] values = new []{1,2,3,4,5,4,4,3};
var groups = values.GroupBy(v => v);
foreach(var group in groups)
    Console.WriteLine("Value {0} has {1} items", group.Key, group.Count());

This method has advantages in code readability and conciseness but may not be applicable under certain constraints, such as when LINQ is not allowed. It also has O(n) time complexity, but the underlying implementation might involve additional overhead. In practice, the choice between methods depends on specific requirements and constraints.

Summary of Core Knowledge Points

The core knowledge points in this article include: basic techniques for array traversal, application of dictionary data structures in counting, algorithm efficiency analysis (time and space complexity), and comparison of different solutions. By deeply understanding these concepts, readers can better handle similar data processing tasks and optimize code performance. In practice, it is recommended to choose the most appropriate method based on the specific context, such as prioritizing dictionary methods in performance-critical applications or using LINQ when code simplicity is more important.