How Can I Efficiently Remove Duplicates from an Array Without Using Sets?

Efficient Array Duplication Removal Without Sets

In some programming challenges, you may need to remove duplicated values from an array without utilizing pre-built data structures like Set or HashSet. Here's an optimized approach you can consider:

Your provided implementation performs multiple passes over the array, leading to inefficient time complexity. To improve it, consider using a combination of two optimizations:

1. Use a Marker Array:

Create a marker array of size equal to the maximum element in the original array. Initialize all elements to 0. When you encounter an element in the original array, set the corresponding position in the marker array to 1. This way, you only need to check the marker array to determine if an element is a duplicate or not.

2. Use End Index Pointer:

Maintain an end index pointer that indicates the index up to which the array without duplicates has been computed. When you encounter a duplicate, shift the elements after the duplicate to the left, decrementing the end index accordingly.

Here's an optimized version of your code using these optimizations:

public static int[] removeDuplicates(int[] arr) {
    // Initialize the marker array with zeros
    int[] marker = new int[1000000];
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        // Check if the element is already marked as duplicate
        if (marker[arr[i]] == 1) {
            // If it's a duplicate, shift the elements after it to the left
            for (int j = i + 1; j < end; j++, i++) {
                arr[i] = arr[j];
            }
            end--;
            i--;
        } else {
            // If it's not a duplicate, mark it in the marker array
            marker[arr[i]] = 1;
        }
    }

    return arr;
}

This implementation significantly improves performance by avoiding multiple passes over the array and reducing the number of element swaps required.

The above is the detailed content of How Can I Efficiently Remove Duplicates from an Array Without Using Sets?. For more information, please follow other related articles on the PHP Chinese website!