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 methodremoveDuplicatesII() 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.
publicclassMain {publicstaticvoidmain(String[]args) {// Test cases with expected outputsSystem.out.println(removeDuplicatesI(newint[] {1,2,3}));// Expected Output: 3System.out.println(removeDuplicatesI(newint[] {1,2,2}));// Expected Output: 2// ... other test cases ... }staticintremoveDuplicatesI(int[]nums) {if (nums.length ==0)return0;intcurrentUniqueNum =nums[0];intuniqueNumPtr =0;for (inti =1;i <nums.length; ++i) {if (nums[i] !=currentUniqueNum) {currentUniqueNum =nums[i];nums[++uniqueNumPtr] =currentUniqueNum; } }returnuniqueNumPtr +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 duplicatesSystem.out.println(removeDuplicatesI(newint[] {1,2,3}));// Expected Output: 3// Test case 2: Consecutive duplicatesSystem.out.println(removeDuplicatesI(newint[] {1,2,2}));// Expected Output: 2// Test case 3: Non-consecutive duplicatesSystem.out.println(removeDuplicatesI(newint[] {1,2,2,3,3,4}));// Expected Output: 4// Test case 4: All elements are duplicatesSystem.out.println(removeDuplicatesI(newint[] {2,2,2,2}));// Expected Output: 1// Test case 5: Single elementSystem.out.println(removeDuplicatesI(newint[] {1}));// Expected Output: 1// Test case 6: Empty arraySystem.out.println(removeDuplicatesI(newint[] {}));// Expected Output: 0// Test case 7: Longer array with mixed duplicatesSystem.out.println(removeDuplicatesI(newint[] {1,1,2,3,3,3,4,5,5,6}));// Expected Output: 6// Test case 8: Array with all elements being the sameSystem.out.println(removeDuplicatesI(newint[] {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.
staticintremoveDuplicatesII(int[]nums) {// Handle empty arraysintarrSize =nums.length;if (arrSize ==0) {return0; }// Adjust the desired frequency of allowed duplicatesintLIMIT =2;// Store the first numberintcurrentUniqueNum =nums[0];intuniqueNumPtr =0;intduplicateCounter =1;for (inti =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; } }returnuniqueNumPtr +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 duplicatesSystem.out.println(removeDuplicatesII(newint[] {1,2,2,3,3,4}));// Expected Output: 6// Test case 2: Consecutive duplicatesSystem.out.println(removeDuplicatesII(newint[] {1,1,2,2,2,3,3,3,4}));// Expected Output: 7// Test case 3: No duplicatesSystem.out.println(removeDuplicatesII(newint[] {1,2,3,4,5}));// Expected Output: 5// Test case 4: Empty arraySystem.out.println(removeDuplicatesII(newint[] {}));// Expected Output: 0// Test case 5: All elements are the sameSystem.out.println(removeDuplicatesII(newint[] {2,2,2,2,2}));// Expected Output: 2// Test case 6: Single element arraySystem.out.println(removeDuplicatesII(newint[] {7}));// Expected Output: 1