Remove duplicates from an Array without Using Set
To remove duplicate elements from an Array without using a Set in Java, we can follow the below algorithm:
Algorithm
- Sort the input array using the Arrays. sort method
- Initialize a variable j, to keep track of the last index of unique elements.
- Iterate through the array, starting from the index 1.
- If the current element is different than the element at index j
- Update j and move a unique element to the next position
- Return a copy of the array, up to index j, which will contain only unique elements.
Java Program to Remove Duplicated from an Array without Using Set
The following program demonstrates how we can remove duplicates from an array without using a set in Java:
// Java Program to Remove Duplicates
// From an Array without Using Set
import java.util.Arrays;
// Driver Class
public class RemoveDuplicates {
// Function to remove duplicates from an arary
public static int[] removeDuplicates(int[] arr) {
// Sort the array
Arrays.sort(arr);
// Initialize the j pointer
int j = 0;
// Start iterating the array from the 1st index
for (int i = 1; i < arr.length; i++) {
if (arr[i] != arr[j]) {
j++;
// Move unique element to the next position
arr[j] = arr[i];
}
}
// Return copy of array upto index j without duplicates
return Arrays.copyOf(arr, j + 1);
}
// Main Function
public static void main(String[] args) {
// Initialize an array
int[] arr = {1,2,2,3,3,3,4,5,5,6};
// Remove duplicates from the array
int[] result = removeDuplicates(arr);
// Print the original array
System.out.println("Original Array: "+Arrays.toString(arr));
// Print the updated array
System.out.println("Array without Duplicates: " +Arrays.toString(result));
}
}
Output
Original Array: [1, 2, 3, 4, 5, 6, 4, 5, 5, 6] Array without Duplicates: [1, 2, 3, 4, 5, 6]
Complexity of the above Method:
Time Complexity: O(N logN), where N is the size of the array.
Auxiliary Space: O(K), where K is the size of the array without duplicate elements.
How to Efficiently Remove Duplicates from an Array without using Set?
Arrays are a fundamental data structure in Java that stores data of the same type in contiguous memory locations. Removing duplicate elements from an array is a common operation that can be easily accomplished using sets. However, in this article, we will learn how to remove duplicates from an array in Java without using a set, in an efficient manner.
Example to Efficiently Remove Duplicates from an Array
Input: arr[] ={ 1,2,2,3,3,3,4,5,5,6}
Output: arr[]= {1,2,3,4,5,6}