This Java project implements an efficient algorithm to remove duplicate numbers from a sorted array in-place, preserving the order of the elements. The key challenge addressed is modifying the array so that the first k elements contain the unique elements as they originally appeared in the array.
The second method removeDuplicatesII() removes duplicates from a sorted array while allowing a specified number of duplicates for each unique element.
- The algorithm uses a two-pointer approach: one pointer (uniqueNumPtr) to track the position where the next unique element should be placed, and the other to iterate through the array.
- As it finds a unique element (different from the previous one), it places it at the uniqueNumPtr position.
- This approach ensures in-place modification of the array with minimal space usage.
- Time Complexity: O(n) - as the array is iterated through only once.
- Space Complexity: O(1) - as no additional space is used apart from the input array.
public class Main {
public static void main(String[] args) {
// Test cases with expected outputs
System.out.println(removeDuplicatesI(new int[] {1, 2, 3})); // Expected Output: 3
System.out.println(removeDuplicatesI(new int[] {1, 2, 2})); // Expected Output: 2
// ... other test cases ...
}
static int removeDuplicatesI(int[] nums) {
if (nums.length == 0) return 0;
int currentUniqueNum = nums[0];
int uniqueNumPtr = 0;
for (int i = 1; i < nums.length; ++i) {
if (nums[i] != currentUniqueNum) {
currentUniqueNum = nums[i];
nums[++uniqueNumPtr] = currentUniqueNum;
}
}
return uniqueNumPtr + 1;
}
}The following test cases are designed to validate the functionality of the removeDuplicatesI method. Each test case includes the input array and its expected output after removing duplicates.
// Test case 1: No duplicates
System.out.println(removeDuplicatesI(new int[] {1, 2, 3})); // Expected Output: 3
// Test case 2: Consecutive duplicates
System.out.println(removeDuplicatesI(new int[] {1, 2, 2})); // Expected Output: 2
// Test case 3: Non-consecutive duplicates
System.out.println(removeDuplicatesI(new int[] {1, 2, 2, 3, 3, 4})); // Expected Output: 4
// Test case 4: All elements are duplicates
System.out.println(removeDuplicatesI(new int[] {2, 2, 2, 2})); // Expected Output: 1
// Test case 5: Single element
System.out.println(removeDuplicatesI(new int[] {1})); // Expected Output: 1
// Test case 6: Empty array
System.out.println(removeDuplicatesI(new int[] {})); // Expected Output: 0
// Test case 7: Longer array with mixed duplicates
System.out.println(removeDuplicatesI(new int[] {1, 1, 2, 3, 3, 3, 4, 5, 5, 6})); // Expected Output: 6
// Test case 8: Array with all elements being the same
System.out.println(removeDuplicatesI(new int[] {7, 7, 7, 7, 7})); // Expected Output: 1- Processes a sorted array to remove duplicates.
- Maintains a counter for duplicates.
- Shifts unique elements to the beginning of the array.
- Time Complexity: O(n) - Processes each element once.
- Space Complexity: O(1) - In-place operation with constant space.
static int removeDuplicatesII(int[] nums) {
// Handle empty arrays
int arrSize = nums.length;
if (arrSize == 0) { return 0; }
// Adjust the desired frequency of allowed duplicates
int LIMIT = 2;
// Store the first number
int currentUniqueNum = nums[0];
int uniqueNumPtr = 0;
int duplicateCounter = 1;
for (int i = 1; i < arrSize; ++i) {
if (nums[i] != currentUniqueNum) {
duplicateCounter = 1;
currentUniqueNum = nums[i];
nums[++uniqueNumPtr] = currentUniqueNum;
}
else {
if (duplicateCounter < LIMIT) {
currentUniqueNum = nums[i];
nums[++uniqueNumPtr] = currentUniqueNum;
}
++duplicateCounter;
}
}
return uniqueNumPtr + 1;
}The following test cases are designed to validate the functionality of the removeDuplicatesI method. Each test case includes the input array and its expected output after removing duplicates.
// Test case 1: Non-consecutive duplicates
System.out.println(removeDuplicatesII(new int[] {1, 2, 2, 3, 3, 4})); // Expected Output: 6
// Test case 2: Consecutive duplicates
System.out.println(removeDuplicatesII(new int[] {1, 1, 2, 2, 2, 3, 3, 3, 4})); // Expected Output: 7
// Test case 3: No duplicates
System.out.println(removeDuplicatesII(new int[] {1, 2, 3, 4, 5})); // Expected Output: 5
// Test case 4: Empty array
System.out.println(removeDuplicatesII(new int[] {})); // Expected Output: 0
// Test case 5: All elements are the same
System.out.println(removeDuplicatesII(new int[] {2, 2, 2, 2, 2})); // Expected Output: 2
// Test case 6: Single element array
System.out.println(removeDuplicatesII(new int[] {7})); // Expected Output: 1
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent