java - Given an unordered stream of integers maintain the ordering but remove the elements that occur exactly once in the array -


my solution:

public class removeuniqueelements {     public static integer[] removeunique(int[] arr){         map<integer,integer> output = new hashmap<integer,integer>();         list<integer> result = new arraylist<integer>();         for(int i=0;i<arr.length;i++){             if(output.containskey(arr[i])){                 int count = output.get(arr[i]);                 count = count+1;                 output.put(arr[i],count);             }             else             {                 output.put(arr[i],1);             }         }         for(int i=0;i<arr.length;i++){             if(output.get(arr[i])!=1){                 result.add(arr[i]);             }         }         return result.toarray(new integer[result.size()]);     }      public static void main(string[] args){         int[] array = {1,2,3,4,2,3,4};         integer[] result = removeunique(array);         system.out.println(arrays.tostring(result));     } } 

time complexity : o(n) space complexity : o(n)

is there other way reduce space complexity? please help.

for better performance, use map<integer, atomicinteger>, can update mapped counter, instead of boxing new value every time increment counter. reduce amount of garbage produced, considered reduction in memory footprint, though technically isn't.

for reduced memory footprint, don't use list<integer> or integer[]. boxing values integer lot of object overhead, , creating list first, final array, means consuming 2 times number of references.

instead, once map has been built, count number of values removed, create result array directly , fill it. no boxing , no space wasted on list.

i'll leave adjust code these improvements.


Comments

Popular posts from this blog

get url and add instance to a model with prefilled foreign key :django admin -

css - Make div keyboard-scrollable in jQuery Mobile? -

ruby on rails - Seeing duplicate requests handled with Unicorn -