Question

In: Computer Science

You are given an array of n elements, and you notice that some of them are...

You are given an array of n elements, and you notice that some of them are duplicates, that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O( n log2 n ).

Solutions

Expert Solution

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

A simple modification to merge sort will do the trick. Merge sort is O(n log n). It's also stable, meaning that items with equal keys will remain in their same relative order. The only difference here is that you want to eliminate duplicates. The only change to the code is in the comparison and copying of items.

You would modify the code so you don't copy equal items:

while (leftIndex < leftMax && rightIndex < rightMax)
{
    if (a[leftIndex] < a[rightIndex])
    {
        output[outputIndex] = a[leftIndex];
        ++leftIndex;
    }
    else if (a[leftIndex] > a[rightIndex])
    {
        output[outputIndex] = a[rightIndex];
        ++rightIndex;
    }
    else
    {
        // items are equal.
        // increment the right, but don't copy anything
        ++rightIndex;
    }
}

You could also do this with a standard merge sort and then do a final pass over the sorted array to remove duplicates.

Kindly revert for any queries

Thanks.


Related Solutions

Consider the element uniqueness problem: check whether all the elements in a given array of n...
Consider the element uniqueness problem: check whether all the elements in a given array of n elements are distinct answer in pseudo code places
// Given an int array of size elements, determine if there are k elements that add...
// Given an int array of size elements, determine if there are k elements that add up to sum. // The array holds integers, both positive and negative and zero. // It is not possible to add zero elements (that's when k==0) to any sum, not even zero. // It is not possible to add any elements from an empty array. // Must be recursive and not iterative //bool K_element_sum(size_t k, int sum, int arr[], size_t size){}
Given the following array of 8 elements, show the steps to sortthe elements in ascending...
Given the following array of 8 elements, show the steps to sort the elements in ascending order using a radix sort. Fill in each of the following blanks.81   546   677   9   97   12   53   22Adjust with 0s:Buckets for ones digit:Buckets for tens digit:Final Result:
write a recursive algorithm to find the maximum element in an array of n elements and...
write a recursive algorithm to find the maximum element in an array of n elements and analyze its time efficiency. (I am using c++ programming language)
You are given an array of length n that is filled with two symbols (say 0...
You are given an array of length n that is filled with two symbols (say 0 and 1); all m copies of one symbol appear first, at the beginning of the array, followed by all n − m copies of the other symbol. You are to find the index of the first copy of the second symbol in time O(logm). include: code,  proof of correctness, and runtime analysis  
FIRST You are given a binary string x and an array A[1 : n] of binary...
FIRST You are given a binary string x and an array A[1 : n] of binary strings. Assume that x and the elements of A have the same length. Let ⊕ denote the xor operator on binary strings. For example 1010 ⊕ 1101 = 0111, and 1110 ⊕ 1111 = 0001. Assume that xor’ing two strings takes O(1) time. Give a divide-and-conquer algorithm to check if there’s a subarray A[i : j] of A such that A[i] ⊕ · ·...
Suppose you are given an integer c and an array, A, indexed from 1 to n,...
Suppose you are given an integer c and an array, A, indexed from 1 to n, of n integers in the range from 0 to 5n (possibly with duplicates). i.e. 0 <= A[i ] <= 5n " I = {1, .., n}. a.) Write an efficient algorithm that runs in O(n) time in a pseudo code for determining if there are two integers, A[i] and A[j], in A whose sum is c, i.e. c = A[i] + A[j], for 1...
Python - You are given a sorted (from smallest to largest) array A of n distinct...
Python - You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative or zero. Design the fastest algorithm you can for deciding if there is an index i such that A[i] = i.
1. Given an array of integers a dimension n. If the array contains the same number...
1. Given an array of integers a dimension n. If the array contains the same number of even and odd elements get (a1 + an) (a2 + an-1) ... 2. Given an array of integers dimension n. All array elements with even numbers preceding the first element to the maximum, multiplied by the maximum. 3. Given an array of dimension n. Insert after each zero element of the element in the middle (or the amount of secondary elements for even...
Array with Pointers Find Continuous Sub-Array C++ Problem: Given an unsorted array A of size N...
Array with Pointers Find Continuous Sub-Array C++ Problem: Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to the given number. Declare dynamic arrays and use only pointers syntax (no [ ]’s or (ptr+i) stuff.     Input will be the number of input values to enter followed by the sum to compare with. Print out the continuous sub-array of values that are equal to sum or the message ‘No sum found’. There...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT