1

Can anyone help me conceptually understand what options are available to me for the following:

I have an array of int elements, I'm looking for a way that I can see if any of these are duplicates. I am trying to keep time complexity in mind, and want a solution that is in O(n) time.

With this specific boundary in mind, I cannot use a nested for-loop to iterate through all n elements, since this array may contain tens of thousands of indicies.

Any ideas or suggestions that might help me?

Improve this question
4
  • 2
    If you sort them (O(n log n)), then once they are sorted, you only have to compare adjacent items. (Assuming you are looking for duplicates.) Commented Aug 31, 2016 at 12:48
  • 1
    What do you mean "any of these match"? Match what? Do you mean find duplicates? Commented Aug 31, 2016 at 12:49
  • Yes I am looking for duplicate elements. Commented Aug 31, 2016 at 12:49
  • 1
    If all your ints are in a fairly constrained range, you can go through it once (O(n)) and keep counts of the occurrences of each value. Commented Aug 31, 2016 at 12:53

1 Answer 1

Reset to default
2

Make HashSet<T> set from your T[] array. If 

set.size() != array.length

then you have duplicates

Making HashSet has O(n) complexity.

Do not forget about equals and hashcode overriding in T.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Working great for me. Thanks for your input!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.