0
Sponsored Links


Ad by Google
Ok, sometimes while working, we face this problem to find the duplicate elements from an array, and also sometime interviewer just write on paper and asking you to write a program or code logic to find the duplicate elements from a given array and expecting some better solution from you or at-least expecting more than one solutions to discuss about the pros and cons of those.
Of-course you can find duplicate elements from an array with number of different approach, but finding the better one is of-course a tedious task, to find better one you need good understating of time and space complexity and the parameters to calculate the time and space. Like we have seen a solution of balancing parentheses with o(n) time at here.

You can find duplicate elements from an array at-least via two different ways but not only the limited and those are.
  • Brute force method(O(n^2)
  • Set technique(O(n))
Brute force:
Brute force method also know as exhaustive search and easy to implement, it compares each element from an array to all other elements and this has the O(n^2) complexity.

Set technique: 
We know that the hashing technique is very fast, and we have Set api in Collection framework so one can easily utilized any implementation of Set to achieve this task, because set does not allow duplicate element in it. And it has O(n) complexity.

Now lets' implement this
package com.javamakeuse.poc;

import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author javamakeuse
 *
 */
public class ArrayExample {
 static public void findDuplicate(String[] strArray) {
  for (int i = 0; i < strArray.length; i++) {
   for (int j = i + 1; j < strArray.length; j++) {
    if (strArray[i].equals(strArray[j])) {
     System.out.println("found duplicate element at index [" + j + "] " + strArray[i]);
    }
   }
  }

 }

 public static void findDuplicate2(String[] strArray) {
  Set<String> strSet = new HashSet<>();
  for (String elemnt : strArray) {
   if (strSet.add(elemnt) == false) {
    System.out.println("found duplicate elemnt " + elemnt);
   }
  }

 }

 public static void main(String[] args) {
  String[] strArray = new String[] { "one", "two", "three", "one" };
  findDuplicate(strArray);
  findDuplicate2(strArray);
 }
}

Sponsored Links

0 comments:

Post a Comment