Removing duplicates from a sorted array in C# can be efficiently accomplished using a two-pointer technique. Since the array is sorted, duplicates will always be adjacent, making it straightforward to identify and remove them.
Explanation
-
Two Pointers: Use one pointer to traverse the array (the
current
pointer) and another pointer to keep track of the position where the next unique element should be placed (theuniqueIndex
pointer). -
Traverse the Array: As you iterate through the array with the
current
pointer, whenever you encounter a unique element (i.e., it differs from the last unique element found), you place it at theuniqueIndex
position and incrementuniqueIndex
. -
Return the Result: After processing the array, the
uniqueIndex
will represent the count of unique elements, and the modified portion of the array will contain all unique elements.
Code Implementation
Here’s a sample implementation in C#:
using System;
class Program
{
static int RemoveDuplicates(int[] nums)
{
if (nums.Length == 0) return 0;
int uniqueIndex = 1; // Start from the second element
for (int current = 1; current < nums.Length; current++)
{
// Check if the current element is different from the previous one
if (nums[current] != nums[current - 1])
{
nums[uniqueIndex] = nums[current]; // Place the unique element
uniqueIndex++; // Move to the next position for the next unique element
}
}
return uniqueIndex; // The length of the array with unique elements
}
static void Main(string[] args)
{
int[] arr = { 0, 0, 1, 1, 2, 2, 3, 3, 4 };
int newLength = RemoveDuplicates(arr);
Console.WriteLine($"Length of array after removing duplicates: {newLength}");
Console.WriteLine("Modified array: " + string.Join(", ", arr[..newLength])); // Output only unique elements
}
}
How the Code Works
-
Check for Empty Array: If the array is empty, return 0 immediately.
-
Initialize the Unique Index: Set
uniqueIndex
to 1, as the first element is always considered unique. -
Loop Through the Array:
- Start from the second element (index 1) and compare each element to the one before it.
- If the current element is different from the previous element, it means it’s a unique element. Place it at the
uniqueIndex
position and incrementuniqueIndex
.
-
Return the Unique Count: After the loop completes,
uniqueIndex
indicates how many unique elements are in the array. -
Output the Results: In the
Main
method, we print the length of the modified array and display the unique elements.
Complexity
- Time Complexity: O(n), where n is the number of elements in the array. We only make one pass through the array.
- Space Complexity: O(1), since we are modifying the array in place and not using any additional data structures.
This method is efficient and straightforward for removing duplicates from a sorted array.