Відео

Detailed Explanation of the Code for Finding Duplicates in an Array The goal of the problem is to identify all elements in an array that occur more than once and return them in ascending order. If no elements repeat, the function should return an empty array. To achieve this, the provided solution uses a **hash map (unordered_map)** to efficiently count the occurrences of each element in the array. After counting, it extracts the elements that have more than one occurrence and returns them in ascending order. Steps in the Code: 1. Input and Output Format: - The input is an array of integers `arr[]`. - The output is a list of integers that appear more than once, sorted in ascending order. 2. Using a Hash Map (unordered_map): - The core of the approach is to use an `unordered_map` (hash map) to store each element of the array as a key, and its corresponding count as the value. This allows us to efficiently track the frequency of each element in the array. 3. Counting Occurrences: - The program iterates through the array. For each element, it checks if the element is already in the hash map. If it is, the count for that element is incremented. If not, the element is added to the map with an initial count of 1. 4. **Extracting Duplicates**: - After processing all elements, we go through the hash map and check the count of each element. If the count is greater than 1, it means the element is a duplicate, so it is added to a new list, `d`. 5. **Sorting the Duplicates**: - Once all duplicates are collected, they are sorted in ascending order using the `sort` function. Sorting ensures that the final list of duplicates is in the correct order. 6. **Returning the Result**: - Finally, the list `d`, which contains all the duplicates in ascending order, is returned. If there are no duplicates, `d` will remain empty and an empty array is returned. ### Theoretical Walkthrough: 1. **Input Handling**: - Suppose the input is an array `arr = [2, 3, 1, 2, 3]`. 2. **Hash Map Construction**: - We initialize an empty `unordered_map<int, int>` called `mp`. - We traverse the array and build the map `mp`: - After processing `2`, `mp = {2: 1}` - After processing `3`, `mp = {2: 1, 3: 1}` - After processing `1`, `mp = {2: 1, 3: 1, 1: 1}` - After processing `2`, `mp = {2: 2, 3: 1, 1: 1}` - After processing `3`, `mp = {2: 2, 3: 2, 1: 1}` 3. **Identifying Duplicates**: - We iterate through the hash map. For each key-value pair: - If the value (count) is greater than 1, it indicates that the number is a duplicate. - We collect the keys (numbers) that have a count greater than 1 into a vector `d`. - So, for `mp = {2: 2, 3: 2, 1: 1}`, the duplicates are `2` and `3`. 4. **Sorting the Duplicates**: - The vector `d` containing the duplicates is `d = {2, 3}`. - We sort the duplicates using `sort(d.begin(), d.end())`, but since `d` is already in ascending order, no change is made. The sorted list remains `d = {2, 3}`. 5. **Returning the Result**: - The sorted list `d = {2, 3}` is returned as the final output. ### Handling Edge Cases: 1. **Empty Input**: - If the array is empty, the map will be empty and no duplicates will be found. The function will return an empty list. 2. **No Duplicates**: - If all elements in the array are unique, the map will have all elements with a count of 1. The result will be an empty list because no element will have a count greater than 1. 3. **Single Element**: - If the array has only one element, there can’t be any duplicates, so the function will return an empty list. 4. **Large Input Size**: - The function is efficient enough to handle the constraints, where the array size can be as large as 10^6. The use of a hash map ensures that counting occurrences is done in O(n) time, and sorting the duplicates takes O(m log m), where m is the number of duplicates. In the worst case, m is much smaller than n. ### Example Walkthrough: #### Example 1: - **Input**: `arr = [2, 3, 1, 2, 3]` - **Map Construction**: `mp = {2: 2, 3: 2, 1: 1}` - **Duplicates**: Extract `2` and `3` into `d = {2, 3}` - **Sorted Duplicates**: `d = {2, 3}` (Already sorted) - **Output**: `[2, 3]` #### Example 2: - **Input**: `arr = [0, 3, 1, 2]` - **Map Construction**: `mp = {0: 1, 3: 1, 1: 1, 2: 1}` - **Duplicates**: No duplicates found. - **Output**: `[]` #### Example 3: - **Input**: `arr = [2]` - **Map Construction**: `mp = {2: 1}` - **Duplicates**: No duplicates found. - **Output**: `[]` ### Time and Space Complexity: - **Time Complexity**: - **Counting occurrences**: O(n), where `n` is the size of the array, as we traverse the array once. - **Sorting the duplicates**: O(m log m), where `m` is the number of duplicates. In the worst case, this is O(n log n), but typically much smaller than n. - **Total**: O(n + m log m) - **Space Complexity**: - The space complexity is O(n) due to the space used by the hash map and the list to store duplicates. ### Conclusion: This solution efficiently counts the occurrences of each element using a hash map and identifies duplicates. It handles edge cases gracefully and is capable of working with large arrays within the given constraints.