I can't seem to wrap my brain around this, but lets say I'm given an array with different elements in it. If I wanted to create another array with only the unique elements from the first array, how would I go about doing that without using Maps, HashSets etc (without importing anything else from java).
2 Answers
Simple brute force algorithm.
Just (double) loop over the array and check if is element is repeated or not. If not add it to the array and continue. O(N^2) complexity instead of O(N) complexity using a Map or Set
5 Comments
nhahtdh
O(N) is only achievable with
HashMap. It will be O(Nlog N) with TreeMap
Luiggi Mendoza
@nhahtdh
O(N) using a Map? I though it was O(1).nhahtdh
@LuiggiMendoza: The N is for the N elements in the array. Operation on HashMap (add) is O(1) amortized.
2to1mux
This will work, but O(N^2) is kind of slow. Doing a sort on the array first, and then looping through would give O(N*lgN). Edit: Harpun's comment above gives this as answer. Just noticed. That's the best solution I think.
Cratylus
@2to1mux:I agree sorting is better.But the OP says he does not want to import anything.So he would have to implement one of the sorting methods for this
Please don't up-vote this, see Cratylus's answer - or better, harpun's comment. This is just some "pseudocode" for a solution with O(n2) complexity.
foreach element1 in array:
duplicate = false
foreach element2 in array:
if element 1 == element 2:
duplicate = true
break // out of inner loop
if duplicate:
// duplicate
else:
// not duplicate
Of course this can be more cleanly expressed at a slightly higher level. The definition of "contains" should be evident.
foreach element in array:
if contains(array, element):
// duplicate
Object#equalsor ajava.util.Comparatorin order to check if the object to be inserted is already in your array.O(N*logN).