How to efficiently remove duplicates from an array without using Set

Question

I was asked to write my own implementation to remove duplicated values in an array  Here is what I have created  But after tests with 1 000 000 elements it took very long time to finish  Is there something that I can do to improve my algorithm or any bugs to remove     I need to write my own implementation - not to use Set  HashSet etc  Or any other tools such as iterators  Simply an array to remove duplicates   public static int   removeDuplicates int   arr         int end   arr length       for  int i   0  i  lt  end  i              for  int j   i   1  j  lt  end  j                  if  arr i     arr j                                       int shiftLeft   j                  for  int k   j 1  k  lt  end  k    shiftLeft                          arr shiftLeft    arr k                                     end--                  j--                                     int   whitelist   new int end       for int i   0  i  lt  end  i             whitelist i    arr i             return whitelist

User · Answer

import java util Arrays   public class Practice    public static void main String   args        int a       1  3  3  4  2  1  5  6  7  7  8  10        Arrays sort a       int j   0      for  int i   0  i  lt  a length - 1  i              if  a i     a i   1                 a j    a i               j                        a j    a a length - 1       for  int i   0  i  lt   j  i              System out println a i                 This is the most simplest way

User · Answer

public static void main String   args                 int input       1  5  1  0  -3  1  -3  2  1                 int j   0               int output     new int 100                Arrays fill a  0                for  int i   0  i  lt  9  i                           if  output input i      0                                input j      input i                                output input i                                                         for  int i   0  i  lt  j  i                           System out print input i

User · Answer

int tempvar 0    Variable for the final array without any duplicates      int whilecount 0       variable for while loop      while whilecount lt  nsprtable 2 -1    nsprtable can be any number          to check whether the next value is idential in case of sorted array        if temparray whilecount   temparray whilecount 1                         finalarray tempvar  temparray whilecount               tempvar                whilecount whilecount 1                    else if  temparray whilecount   temparray whilecount 1                         finalarray tempvar  temparray whilecount               tempvar                whilecount whilecount 2                     Hope this helps or solves the purpose

User · Answer

Here is my solution  The time complexity is o n 2   public String removeDuplicates char   arr            StringBuilder sb   new StringBuilder             if  arr    null              return null          int len   arr length           if  arr length  lt  2              return sb append arr 0   toString             for  int i   0  i  lt  len  i                   for  int j   i   1  j  lt  len  j                      if  arr i     arr j                         arr j    0                                               if  arr i     0                  sb append arr i                       return sb toString   trim

User · Answer

For a sorted Array  just check the next index     sorted data  public static int   distinct int   arr        int   temp   new int arr length        int count   0      for  int i   0  i  lt  arr length  i              int current   arr i            if count  gt  0               if temp count - 1     current                  continue           temp count    current          count               int   whitelist   new int count       System arraycopy temp  0  whitelist  0  count        return whitelist

User · Answer

public static void main String   args            Integer   intArray     1  1  1  2  4  2  3  5  3  6  7  3  4  5            Integer   finalArray   removeDuplicates intArray           System err println Arrays asList finalArray               private static Integer   removeDuplicates Integer   intArray            int count   0          Integer   interimArray   new Integer intArray length           for  int i   0  i  lt  intArray length  i                  boolean exists   false              for  int j   0  j  lt  interimArray length  j                      if  interimArray j   null  amp  amp  interimArray j     intArray i                         exists   true                                              if   exists                    interimArray count    intArray i                   count                                    final Integer   finalArray   new Integer count           System arraycopy interimArray  0  finalArray  0  count           return finalArray

User · Answer

class Demo        public static void main String   args                 int a    3 2 1 4 2 1           System out print  Before Sorting             for  int i 0 i lt a length  i                           System out print a i    t                      System out print    nAfter Sorting               sorting the elements         for int i 0 i lt a length i                          for int j i j lt a length j                                  if a i  gt a j                                         int temp a i                       a i  a j                       a j  temp                                                        After sorting         for int i 0 i lt a length i                          System out print a i    t                      System out print   nAfter removing duplicates             int b 0          a b  a 0           for int i 0 i lt a length i                          if  a b   a i                                 b                    a b  a i                                   for  int i 0 i lt  b i                           System out print a i    t                        OUTPUT Before Sortng 3 2 1 4 2 1 After Sorting 1 1 2 2 3 4                  Removing Duplicates 1 2 3 4

User · Answer

public static int   removeDuplicates int   arr       HashSet lt Integer gt  set   new HashSet lt  gt         final int len   arr length        changed end to len     for int i   0  i  lt  len  i             set add arr i               int   whitelist   new int set size         int i   0      for  Iterator lt Integer gt  it   set iterator    it hasNext               whitelist i      it next              return whitelist      Runs in O N  time instead of your O N 3  time

User · Answer

Since this question is still getting a lot of attention  I decided to answer it by copying this answer from Code Review SE      You re following the same philosophy as the bubble sort  which is   very  very  very slow  Have you tried this           Sort your unordered array with quicksort  Quicksort is much faster   than bubble sort  I know  you are not sorting  but the algorithm you   follow is almost the same as bubble sort to traverse the array      Then start removing duplicates  repeated values will be next to each   other   In a for loop you could have two indices  source and   destination   On each loop you copy source to destination unless they   are the same  and increment both by 1   Every time you find a   duplicate you increment source  and don t perform the copy      morgano

User · Answer

Well first answer will be to use hashset which is designed to remove duplicates as Android Killer answer pointed out  Approach 2  - But if you are not allowed to use set then sort it first with quicksort which will be nlogn and then apply XOR operation to find duplicates  Optimized one   public static void removeDuplicates int   arr            int   input   new int     1  1  3  7  7  8  9  9  9  10            int current   input 0           boolean found   false           for  int i   0  i  lt  input length-1  i                   if  input i  input i 1    0                   System out println input i

User · Answer

Heres a simpler  better way to do this using arraylists instead   public static final  lt T gt  ArrayList lt T gt  removeDuplicates ArrayList lt T gt  in       ArrayList lt T gt  out   new ArrayList lt T gt         for T t   in           if  out contains t                out add t       return out

User · Answer

If you are looking to remove duplicates using the same array and also keeping the time complexity of O n   Then this should do the trick  Also  would only work if the array is sorted  function removeDuplicates sorted arr    let j   0    for let x   0  x  lt  arr length - 1  x              if arr x     arr x   1             arr j      arr x            arr j      arr arr length - 1   arr length   j   return arr     Here is for an unsorted array  its O n  but uses more space complexity then the sorted  function removeDuplicates unsorted arr    let map       let j   0   for var numbers of arr       if  map numbers            map numbers    1          arr j      numbers           arr length   j   return arr

User · Answer

What if you create two boolean arrays  1 for negative values and 1 for positive values and init it all on false   Then you cycle thorugh the input array and lookup in the arrays if you ve encoutered the value already  If not  you add it to the output array and mark it as already used

User · Answer

Hope it helps     if   checked   Condition to add into array            scope selectWeekDays push WeekKeys         else           for  i   0  i  lt    scope selectWeekDays length  i       Loop to check IsExists               if   scope selectWeekDays i     WeekKeys   then if Equals removing by splice                    scope selectWeekDays splice i  1                   break

User · Answer

public static void main String args          int   intarray    1 2 3 4 5 1 2 3 4 5 1 2 3 4 5        Set lt Integer gt  set   new HashSet lt Integer gt         for int i   intarray            set add i              Iterator lt Integer gt  setitr   set iterator        for int pos 0  pos  lt  intarray length  pos               if pos  lt  set size                  intarray pos   setitr next              else               intarray pos   0                       for int i  intarray      System out println i

User · Answer

package com pari practice   import java util HashSet  import java util Iterator   import com pari sort Sort   public class RemoveDuplicates            brute force- o N square          param input     return     public static int   removeDups int   input       boolean   isSame   new boolean input length       int sameNums   0       for  int i   0  i  lt  input length  i              for  int j   i 1  j  lt  input length  j                 if  input j     input i       compare same                 isSame j    true                  sameNums                                         compact the array into the result      int   result   new int input length-sameNums       int count   0      for  int i   0  i  lt  input length  i              if  isSame i     true                continue                    else              result count    input i               count                         return result            set - o N     does not guarantee order of elements returned - set property         param input     return     public static int   removeDups1 int   input       HashSet myset   new HashSet         for  int i   0  i  lt  input length  i              myset add input i                 compact the array into the result      int   result   new int myset size         Iterator setitr   myset iterator        int count   0      while  setitr hasNext              result count     int  setitr next            count           return result            quicksort - o Nlogn          param input     return     public static int   removeDups2 int   input       Sort st   new Sort        st quickSort input  0  input length-1     input is sorted        compact the array into the result      int   intermediateResult   new int input length       int count   0      int prev   Integer MIN VALUE      for  int i   0  i  lt  input length  i              if  input i     prev                intermediateResult count    input i               count                      prev   input i              int   result   new int count       System arraycopy intermediateResult  0  result  0  count        return result      public static void printArray int   input       for  int i   0  i  lt  input length  i              System out print input i                   public static void main String   args       int   input    5 6 8 0 1 2 5 9 11 0       RemoveDuplicates printArray RemoveDuplicates removeDups input        System out println        RemoveDuplicates printArray RemoveDuplicates removeDups1 input        System out println        RemoveDuplicates printArray RemoveDuplicates removeDups2 input          Output  5 6 8 0 1 2 9 11   0 1 2 5 6 8 9 11   0 1 2 5 6 8 9 11   I have just written the above code for trying out  thanks

User · Answer

Since you can assume the range is between 0-1000 there is a very simple and efficient solution    Throws an exception if values are not in the range of 0-1000 public static int   removeDuplicates int   arr        boolean   set   new boolean 1001     values must default to false     int totalItems   0       for  int i   0  i  lt  arr length    i            if   set arr i                  set arr i     true              totalItems                         int   ret   new int totalItems       int c   0      for  int i   0  i  lt  set length    i            if  set i                 ret c      i                      return ret      This runs in linear time O n   Caveat  the returned array is sorted so if that is illegal then this answer is invalid

User · Answer

You need to sort your array then then loop and remove duplicates  As you cannot use other tools you need to write be code yourself   You can easily find examples of quicksort in Java on the internet  on which this example is based    public static void main String   args  throws Exception       final int   original   new int   1  1  2  8  9  8  4  7  4  9  1       System out println Arrays toString original        quicksort original       System out println Arrays toString original        final int   unqiue   new int original length       int prev   original 0       unqiue 0    prev      int count   1      for  int i   1  i  lt  original length    i            if  original i     prev                unqiue count      original i                     prev   original i             System out println Arrays toString unqiue        final int   compressed   new int count       System arraycopy unqiue  0  compressed  0  count       System out println Arrays toString compressed       private static void quicksort final int   values        if  values length    0            return            quicksort values  0  values length - 1      private static void quicksort final int   values  final int low  final int high        int i   low  j   high      int pivot   values low    high - low    2       while  i  lt   j            while  values i   lt  pivot                i                      while  values j   gt  pivot                j--                    if  i  lt   j                swap values  i  j               i                j--                      if  low  lt  j            quicksort values  low  j             if  i  lt  high            quicksort values  i  high            private static void swap final int   values  final int i  final int j        final int temp   values i       values i    values j       values j    temp      So the process runs in 3 steps    Sort the array  - O nlgn  Remove duplicates - O n  Compact the array - O n    So this improves significantly on your O n 3  approach   Output    1  1  2  8  9  8  4  7  4  9  1   1  1  1  2  4  4  7  8  8  9  9   1  2  4  7  8  9  0  0  0  0  0   1  2  4  7  8  9    EDIT  OP states values inside array doesn t matter really  But I can assume that range is between 0-1000  This is a classic case where an O n  sort can be used   We create an array of size range  1  in this case 1001  We then loop over the data and increment the values on each index corresponding to the datapoint   We can then compact the resulting array  dropping values the have not been incremented  This makes the values unique as we ignore the count   public static void main String   args  throws Exception       final int   original   new int   1  1  2  8  9  8  4  7  4  9  1  1000  1000       System out println Arrays toString original        final int   buckets   new int 1001       for  final int i   original            buckets i               final int   unique   new int original length       int count   0      for  int i   0  i  lt  buckets length    i            if  buckets i   gt  0                unique count      i                      final int   compressed   new int count       System arraycopy unique  0  compressed  0  count       System out println Arrays toString compressed        Output    1  1  2  8  9  8  4  7  4  9  1  1000  1000   1  2  4  7  8  9  1000

User · Answer

How about this one  only for sorted array of numbers  to print array without duplicates  without using Set or other Collections  just Array     public static int   removeDuplicates int   array        int   nums  new int array length       int addedNum   0      int j 0      for int i 0 i lt array length i              if  addedNum    array i             nums j    array i           j            addedNum   nums j-1                       return Arrays copyOf nums  j       Array of 1040 duplicated numbers processed in 33020 nanoseconds 0 033020 millisec

User · Answer

Use the ArrayUtil class as you need  I have written some methods other than removing duplicates  This class is implemented without using any Collection framework classes   public class ArrayUtils          Removes all duplicate elements from an array       param arr Array from which duplicate elements are to be removed      param removeAllDuplicates true if remove all duplicate values  false otherwise      return Array of unique elements      public static int   removeDuplicate int   arr  boolean removeAllDuplicates                int size   arr length       for  int i   0  i  lt  size             boolean flag   false           for  int j   i   1  j  lt  size                 if  arr i     arr j                     flag   true                  shrinkArray arr  j  size                   size--                else                 j                       if  flag  amp  amp  removeAllDuplicates                shrinkArray arr  i  size               size--            else             i               int unique     new int size       for  int i   0  i  lt  size  i            unique i    arr i        return unique            Removes duplicate elements from an array       param arr Array from which duplicate elements are to be removed      return Array of unique elements      public static int   removeDuplicate int   arr        return removeDuplicate arr  false       private static void shrinkArray int   arr  int pos  int size        for  int i   pos  i  lt  size - 1  i              arr i    arr i   1                   Displays the array      param arr The array to be displayed      public static void displayArray int arr          System out println   n nThe Array Is - n         for  int i   0  i  lt  arr length  i              System out print arr i      t                    Initializes the array with a given value      param arr The array to be initialized      param withValue The value with which the array is to be initialized      public static void initializeArray int   arr  int withValue        for  int i   0  i  lt  arr length  i              arr i    withValue                  Checks whether an element is there in the array       param arr The array in which the element is to be found      param element The element that is to be found      return True if found false otherwise     public static boolean contains int arr    int element        for int i 0  i lt  arr length  i              if arr i     element              return true             return false            Removes a element from an array      param arr The array from which the element is to removed      param element The element to be removed     return The size of the array after removing      public static int removeElement int   arr  int element        int size   arr length      for int i 0  i lt  arr length  i             if arr i     element               shrinkArray arr  i  arr length               size--                      return size            Counts unique elements in an array      param arr The required array      return Unique element count      public static int uniqueElementCount int arr          int count   0      int uniqueCount 0      int   consideredElements   new int arr length        initializeArray consideredElements  0        for int i 0 i lt arr length i              int element   arr i           for int j i 1 j lt arr length  j                 if element    arr j   amp  amp   contains consideredElements  element                    consideredElements count      element                                     for int i 0 i lt  consideredElements length i            if consideredElements i   0              uniqueCount         return uniqueCount

User · Answer

The most efficient way to remove duplicates from integer array without using set is  just create a temp array and iterate the original array and check if number exists in temp array then do not push into array else put into temp array and return temp array as result  Please consider the following code snippet    package com numbers   import java util Arrays   public class RemoveDuplicates       public int   removeDuplicate int   array            int   tempArray   new int array length           int j   0          for  int i   array                if   isExists tempArray  i                     tempArray j      i                                  return tempArray             public static boolean isExists int   array  int num            if  array    null              return false          for  int i   array                if  i    num                    return true                                  return false             public static void main String   args            int    array     10  20  30  10  45  30            RemoveDuplicates duplicates   new RemoveDuplicates            System out println  Before removing duplicates       Arrays toString array            int    newArray   duplicates removeDuplicate array           System out println  After removing duplicates       Arrays toString newArray

User · Answer

public static int   removeDuplicates int   input            int j   0          int i   1            return if the array length is less than 2         if input length  lt  2               return input                    while i  lt  input length               if input i     input j                    i                 else                  j   j 1                  input j    input i                   i   i 1                                      int   output   new int j 1           for int k 0  k lt output length  k                 output k    input k                      return output         public static void main String a             int   input1    2 3 6 6 8 9 10 10 10 12 12           int   output   removeDuplicates input1           for int i output               System out println i

User · Answer

Slight modification to the original code itself  by removing the innermost for loop   public static int   removeDuplicates int   arr       int end   arr length       for  int i   0  i  lt  end  i              for  int j   i   1  j  lt  end  j                  if  arr i     arr j                                         int shiftLeft   j                  for  int k   j 1  k  lt  end  k    shiftLeft                          arr shiftLeft    arr k                                       arr j    arr end-1                   end--                  j--                                     int   whitelist   new int end         for int i   0  i  lt  end  i             whitelist i    arr i               System arraycopy arr  0  whitelist  0  end       return whitelist

User · Answer

Just a trick to remove duplicates   public class RemoveDuplicates       public static void main String   args            int   arr    2 2 2 2 2 5 9  4 5 6 1 6 6 2 4 7           arr   removeDuplicates arr               print arr              public static int   removeDuplicates int    arr            final int garbage   -2147483648          int duplicates   0           for int i 0  i lt arr length  i                  for int j i 1  j lt arr length  j                      if  arr i     arr j                         arr i    garbage                      duplicates                                                       int   nArr   new int arr length - duplicates           int nItr   0          for int i 0  i lt arr length  i                  if  arr i     garbage                    nArr nItr    arr i                   nItr                                     return nArr             public static void print int    arr            for  int n   arr                System out print n     t

User · Answer

Why do all people not check this below lines   I need to write my own implementation - not to use Set  HashSet etc  Or any other tools such as iterators  Simply an array to remove duplicates    I m posting very simple implementation with caring the above line   public class RemoveDuplicates    public static void main String   args         int   arr     1  2  3  4  2  3  1       input array     int len   arr length      for  int i   0  i  lt  arr length  i              for  int j   i   1  j  lt  len  j                  if  arr i     arr j                     while  j  lt   len  - 1                        arr j    arr j - 1                       j                                      len--                                    for  int i   0  i  lt  len  i              System out print       arr i                        Input    1  2  3  4  2  3  1      Output     1  2  3  4

User · Answer

Not a big fun of updating user input  however considering your constraints     public int   removeDup int   nums      Arrays sort nums     int x   0    for  int i   0  i  lt  nums length  i          if  i    0    nums i     nums i - 1         nums x      nums i               return Arrays copyOf nums  x       Array sort can be easily replaced with any nlog n  algorithm

User · Answer

Okay  so you cannot use Set or other collections   One solution I don t see here so far is one based on the use of a Bloom filter  which essentially is an array of bits  so perhaps that passes your requirements   The Bloom filter is a lovely and very handy technique  fast and space-efficient  that can be used to do a quick check of the existence of an element in a set without storing the set itself or the elements   It has a  typically small  false positive rate  but no false negative rate   In other words  for your question  if a Bloom filter tells you that an element hasn t been seen so far  you can be sure it hasn t   But if it says that an element has been seen  you actually need to check   This still saves a lot of time if there aren t too many duplicates in your list  for those  there is no looping to do  except in the small probability case of a false positive --you typically chose this rate based on how much space you are willing to give to the Bloom filter  rule of thumb  less than 10 bits per unique element for a false positive rate of 1     There are many implementations of Bloom filters  see e g  here or here  so I won t repeat that in this answer   Let us just assume the api described in that last reference  in particular  the description of put E e       true if the Bloom filter s bits changed as a result of this operation  If the bits changed  this is definitely the first time object has been added to the filter  If the bits haven t changed  this might be the first time object has been added to the filter          An implementation using such a Bloom filter would then be   public static int   removeDuplicates int   arr        ArrayList lt Integer gt  out   new ArrayList lt  gt         int n   arr length      BloomFilter lt Integer gt  bf   new BloomFilter lt  gt            decide how many bits and how many hash functions to use  compromise between space and false positive rate       for  int e   arr            boolean might contain    bf put e           boolean found   false          if  might contain                   check if false positive             for  int u   out                    if  u    e                        found   true                      break                                                    if   found                out add e                       return out stream   mapToInt i - gt  i  toArray        Obviously  if you can alter the incoming array in place  then there is no need for an ArrayList  at the end  when you know the actual number of unique elements  just arraycopy   those

User · Answer

you can take the help of Set collection  int end   arr length  Set lt Integer gt  set   new HashSet lt Integer gt      for int i   0  i  lt  end  i       set add arr i        now if you will iterate through this set  it will contain only unique values  Iterating code is like this    Iterator it   set iterator    while it hasNext        System out println it next

User · Answer

public void removeDup     String   arr     1   1   2   3   3              boolean exists   false            String   arr2   new String arr length             int count1   0            for int loop 0 loop lt arr length loop                                String val   arr loop                 exists   false                for int loop2 0 loop2 lt arr2 length loop2                                           if arr2 loop2   null break                    if arr2 loop2   val                           exists   true                                                  if  exists                        arr2 count1    val                      count1

User · Answer

package javaa   public class UniqueElementinAnArray      public static void main String   args          int   a    10 10 10 10 10 100       int   output   new int a length       int count   0      int num   0         Iterate over an array     for int i 0  i lt a length  i                  num a i           boolean flag   check output num           if flag  false                        output count  num                count                          print the all the elements from an array except zero s  0      for  int i   output                 if i  0               System out print i                          If a next number from an array is already exists in unique array then return true else false     param arr   Unique number array  Initially this array is an empty      param num   Number to be search in unique array  Whether it is duplicate or unique      return  true  If a number is already exists in an array else false      public static boolean check int   arr  int num        boolean flag   false      for int i 0 i lt arr length  i                  if arr i   num                        flag   true              break                      return flag

User · Answer

This is simple way to sort the elements in the array  public class DublicatesRemove       public static void main String args    throws Exception            BufferedReader br   new BufferedReader new InputStreamReader System in            System out println  enter size of the array            int l   Integer parseInt br readLine             int   a   new int l              insert elements in the array logic         for  int i   0  i  lt  l  i                           System out println  enter a element                int el   Integer parseInt br readLine                 a i    el                       sorting elements in the array logic         for  int i   0  i  lt  l  i                           for  int j   0  j  lt  l - 1  j                                   if  a j   gt  a j   1                                         int temp   a j                       a j    a j   1                       a j   1    temp                                                       remove duplicate elements logic         int b   0          a b    a 0           for  int i   1  i  lt  l  i                          if  a b     a i                                 b                    a b  a i                                     for int i 0 i lt  b i                          System out println a i

User · Answer

import java util    class removeDuplicate  int    y    public removeDuplicate int   array       y array        for int b 0 b lt y length b             int temp   y b           for int v 0 v lt y length v                 if  b  v  amp  amp  temp  y v                    y v  0

User · Answer

If you are allowed to use Java 8 streams   Arrays stream arr  distinct   toArray

User · Answer

This is not using Set  Map  List or any extra collection  only two arrays   package arrays duplicates   import java lang reflect Array  import java util Arrays   public class ArrayDuplicatesRemover lt T gt         public static  lt T gt  T   removeDuplicates T   input  Class lt T gt  clazz            T   output    T    Array newInstance clazz  0           for  T t   input                if   inArray t  output                     output   Arrays copyOf output  output length   1                   output output length - 1    t                                  return output             private static  lt T gt  boolean inArray T search  T   array            for  T element   array                if  element equals search                     return true                                  return false             And the main to test it  package arrays duplicates   import java util Arrays   public class TestArrayDuplicates        public static void main String   args            Integer   array    1  1  2  2  3  3  3  3  4           testArrayDuplicatesRemover array              private static void testArrayDuplicatesRemover Integer   array            final Integer   expectedResult    1  2  3  4           Integer   arrayWithoutDuplicates   ArrayDuplicatesRemover removeDuplicates array  Integer class           System out println  Array without duplicates is supposed to be      Arrays toString expectedResult            System out println  Array without duplicates currently is      Arrays toString arrayWithoutDuplicates            System out println  Is test passed ok        Arrays equals arrayWithoutDuplicates  expectedResult     YES     NO                And the output   Array without duplicates is supposed to be   1  2  3  4  Array without duplicates currently is   1  2  3  4  Is test passed ok   YES

User · Answer

public class RemoveDuplicates   public Integer   returnUniqueNumbers Integer   original          Integer   uniqueNumbers        int k   0         for  int j    original length - 1  j  gt   0  j--            boolean present   false          for  Integer u   uniqueNumbers                if  u    null               if u equals original j                      present   true                                   if  present    false                uniqueNumbers k    original j               k                        return uniqueNumbers     public static void main String args          RemoveDuplicates removeDup   new RemoveDuplicates        Integer   original     10  20  40  30  50  40  30  20  10  50  50  50 20 30 10 40        Integer   finalValue   new Integer original length   1           method to return unique values     Integer   unique   removeDup returnUniqueNumbers original  finalValue           iterate to return unique values     for  Integer u   unique            if  u    null                System out println  unique value       u                        This code handles unsorted array containing multiple duplicates for same value and returns unique elements

User · Answer

We can remove duplicates using heap data structure   Create a min Heap or Max heap  I use min Heap  Takes O n   remove the elements from the heap and store it into another list if that element is not in that list  This  takes O nlog n   since we remove an element from the heap and it takes log n we do this  until the all n elements removed from the heap n   logn  Overall Time complexity is O nlog n    Python code for my approach import heapq  l   1 2 4 6 3 2 6 1   heapq heapify l  no duplicate list      try      while True          e   heapq heappop l   will return the minimum value from the heap          if no duplicate list                   no duplicate list append e          else              if e    no duplicate list -1                   continue             no duplicate list append e  except IndexError as i      print no duplicate list    1  2  3  4  6

User · Answer

Please check this  It will work for both sorted unsorted array  The complexity is O n 2  same as bubble sort   Yes the complexity can be improved further with first sort and then binary search  But this is simple enough to work on every cases except negative element  -1   This can also be changed by using large integer value instead of -1   void remove duplicates int  A  int N      int i j   for  i 1  i lt N  i          if  A i     -1  continue      for  j i 1  j lt  N  j              if  A i     A j               A j    -1             int main      int N  int A 1001   int i   printf  Enter N      scanf   d    amp N   printf  Enter the elements  n    for  i 1  i lt  N  i        scanf   d    amp A i     remove duplicates A  N   for  i 1  i lt  N  i          if  A i     -1          continue      printf   d     A i      printf   n     return 0

User · Answer

I feel Android Killer s idea is great  but I just wondered if we can leverage HashMap  So I did a little experiment  And I found HashMap seems faster than HashSet   Here is code       int   input   new int 1000000        for  int i   0  i  lt  input length  i              Random random   new Random            input i    random nextInt 200000              long startTime1   new Date   getTime        System out println  Set start time     startTime1        Set lt Integer gt  resultSet   new HashSet lt Integer gt          for  int i   0  i  lt  input length  i              resultSet add input i               long endTime1   new Date   getTime        System out println  Set end time    endTime1       System out println  result of set      endTime1 - startTime1             System out println  number of Set     resultSet size       n         long startTime2   new Date   getTime        System out println  Map start time     startTime1        Map lt Integer  Integer gt  resultMap   new HashMap lt Integer  Integer gt          for  int i   0  i  lt  input length  i              if   resultMap containsKey input i                resultMap put input i   input i               long endTime2   new Date   getTime        System out println  Map end Time     endTime2       System out println  result of Map      endTime2 - startTime2        System out println  number of Map     resultMap size       Here is result   Set start time 1441960583837 Set end time 1441960583917 result of set 80 number of Set 198652  Map start time 1441960583837 Map end Time 1441960583983 result of Map 66 number of Map 198652

User · Answer

Note  I am assuming the array is sorted   Code   int   input   new int   1  1  3  7  7  8  9  9  9  10   int current   input 0   boolean found   false   for  int i   0  i  lt  input length  i          if  current    input i   amp  amp   found            found   true        else if  current    input i             System out print       current           current   input i           found   false          System out print       current     output     1 3 7 8 9 10

User · Answer

I know this is kinda dead but I just wrote this for my own use  It s more or less the same as adding to a hashset and then pulling all the elements out of it  It should run in O nlogn  worst case       public static int   removeDuplicates int   numbers        Entry   entries   new Entry numbers length       int size   0      for  int i   0   i  lt  numbers length   i              int nextVal   numbers i           int index   nextVal   entries length          Entry e   entries index           if  e    null                entries index    new Entry nextVal               size              else               if e insert nextVal                     size                                      int   result   new int size       int index   0      for  int i   0   i  lt  entries length   i              Entry current   entries i           while  current    null                result i      current value              current   current next                      return result     public static class Entry       int value      Entry next       Entry int value            this value   value             public boolean insert int newVal            Entry current   this          Entry prev   null          while  current    null                if  current value    newVal                    return false                else if current next    null                    prev   current                  current   next                                  prev next   new Entry value           return true

User · Answer

This is an interview question  Remove duplicates from an array I shall not use any Set or collections  The complete solution is    public class Test4   public static void main String   args         int a      1  2  2  3  3  3  6 6 6 6 6 66 7 65                  int newlength      lengthofarraywithoutduplicates a                 for int i   0   i  lt  newlength  i                        System out println a i                     for    main  private static int lengthofarraywithoutduplicates int   a         int count   1        for  int i   1  i  lt  a length  i                int ch   a i             if ch    a i-1                   a count      ch               if        for     return count      fix     end1

User · Answer

There exists many solution of this problem     The sort approach    You sort your array and resolve only unique items   The set approach    You declare a HashSet where you put all item then you have only unique ones    You create a boolean array that represent the items all ready returned   this depend on your data in the array      If you deal with large amount of data i would pick the 1  solution  As you do not allocate additional memory and sorting is quite fast  For small set of data the complexity would be n 2 but for large i will be n log n

User · Answer

I have done using sample as 12 elements    public class Remdup arr    public static void main String   args         int a      1 1 2 3 4 4 5 6 7 8 6 8       for int p   a                System out print p           System out print   t               System out println        System out println         remdup a       private static void remdup int   a         int length   a length      int b     new int 11       int d   1      b 0  a 0       while length lt 13  amp  amp  length gt 0                int x   a length-1           if   contain b   x                 b d    a length-1               d             length--               for  int z   0 z lt b length z             System out print b z            System out print   t         private static boolean contain int   b  int p         boolean bool   false      int len   b length      for int i   0 i lt len i                  if p    b i               bool   true               return bool          output is  - 1   1   2   3   4   4   5   6   7   8   6   8     1   8   6   7   5   4   3   2   0   0   0

User · Answer

public class RemoveDuplicates        public static void main String   args               TODO Auto-generated method stub          int size          System out println  Enter an array size            Scanner sc new Scanner System in           size   sc nextInt             int arr     new int size            System out println  Enter   size   numbers            for int i 0 i lt size i                 arr i  sc nextInt                       for int i 0 i lt size i                 int count 0              for int j i 1 j lt size j                     if arr i   arr j                         int shiftLeft   j                       for  int k   j 1  k  lt  size  k    shiftLeft                              arr shiftLeft    arr k                                             size--                      j--                                                    System out println  New Array            for int i 0 i lt size i                          System out println arr i

User · Answer

public static int   removeDuplicates int   arr     int end   arr length    HashSet lt Integer gt  set   new HashSet lt Integer gt  end       for int i   0   i  lt  end   i             set add arr i          return set toArray

User · Answer

You can use an auxiliary array  temp  which in indexes are numbers of main array  So the time complexity will be liner and O n   As we want to do it without using any library  we define another array  unique  to push non-duplicate elements    x000D   x000D  var num    2 4 9 4 1 2 24 12 4   x000D  let temp       x000D  let unique       x000D  let j   0  x000D  for  let i   0  i  lt  num length  i     x000D    if  temp num i       1   x000D      temp num i     1  x000D      unique j      num i   x000D      x000D    x000D  console log unique   x000D   x000D   x000D

User · Answer

Remove duplicate from sorted array  public class RemDupFromArray       static int num      public static void main String   args           int arr      0 0 2 2 3  5  5 7  7  7           for int i 0 i lt arr length-1 i                 if num  arr i                    num arr i                   System out print arr i

[java] How to efficiently remove duplicates from an array without using Set

Examples related to java

Examples related to arrays

Examples related to optimization