(Is there a O(1) approach.) Given an array of characters, give an algorithm for removing the duplicates

Asked Jul 26 '17 at 15:08

Active Jul 26 '17 at 15:13

Viewed 55 times

Is there a O(1) solution.

Approach :

public void removeDuplicates(char[] a, int n){
   for(int i = 0; i < n; i++){
      for(int j = 0; j < n;){
               if(a[i] == a[j])
                   a[j] = s [--n];
               else  j++;
           }
       }
        s[i] = '\0';
    }

But the time complexity is O(n^2). Can it be optimised further ?

edited Jul 26 '17 at 15:13

asked Jul 26 '17 at 15:08

Gaurav Anand

3

O(n) is going to be your lower bound. There's no way to remove duplicates without looking at each element once. – Bill the Lizard Jul 26 '17 at 15:18
i was wondering what hashing would do. – Gaurav Anand Jul 29 '17 at 14:01
Anyways, O(1) in not possible – Gaurav Anand Jul 29 '17 at 14:02
1

Right. Hashing is a good approach, but you still have to hash all n elements to eliminate duplicates, so you can't get to O(1). – Bill the Lizard Jul 29 '17 at 15:10

(Is there a O(1) approach.) Given an array of characters, give an algorithm for removing the duplicates

0 Answers0