0

Given an array of n random numbers, find a O(n*ln n) algorithm to check if it contains repetitive occurrences of some number using only arrays (no other complex data structures).

I got the obvious O(N*N) when you take each element and compare with the rest to check for a match. You can also sort it and compare adjacent elements in n*log n. I am looking for something other than that.

Improve this question
9
  • 1
    Is this homework? What have you tried? Commented Oct 11, 2013 at 23:26
  • I got the obvious O(NN) when you take each element and compare with the rest to check for a match. You can also sort it and compare adjacent elements in nlog n. I am looking for something other than that. Commented Oct 11, 2013 at 23:29
  • 1
    Hint: What nlogn algorithms have you covered in this course? Commented Oct 11, 2013 at 23:30
  • do you need for find repetitive occurrences in UNsorted array? or just find if any number occurs several times in array Commented Oct 11, 2013 at 23:38
  • @IlyaBursov I wrote the question as it is in 'Introduction to Algorithms' by Cormen. My understanding is to find the first element that repeats twice and return 'Yes'. If no element repeats, return 'No'. The reason I mentioned only arrays (no other DS) and no n*log n sorting is because those topics are not yet covered. Commented Oct 11, 2013 at 23:41

2 Answers 2

Reset to default
3

OK, Let me have a take on this.

  1. Find the largest element(say max) in the array. (O(N) operation)
  2. Create a boolean array(say temp) of size max.
  3. Traverse through the original array and use the current_value as index for temp array and check if it is true i.e. if (temp[current_value] == true)
  4. If it is true you have found the repeating element else set temp[current_value] = true

Obviously this algorithm is not space efficient as we don't know what would be the size of the temp array and most of the spaces in the temp array would never be visited but it's time complexity is O(N)

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

10 Comments

for usual int type, you can have array with 2^32 numbers, which is the whole memory in 32bit cpu
This is probably the best solution without sorting. +1. And if they are 4 byte ints then you can just bound it by 2^32 as Ilya said and then you won't need to calculate the max.
As I said depends on the max number in the array. We can delay the creation of temp array after the max is found in the array to check if we should create an temp array of that size of not.
this solution is called counting sort
Strange I didn't know if there was a name for this approach I cooked it myself. Thanks @IlyaBursov for pointing that out
|
1

It's better to replace the array with a hash table.Then, there is no need to find min/max, just start putting your numbers in the hash table as kyes, checking before each "put" whether that key is already there. Note that the array approach cannot handle numbers in a large range, say min=-2^63, max=2^63, even if there are just a few of them. On the other hand, hash table can handle them easily.

However, I just noticed that you want to use only arrays. Then you can simulate the hash table using the array. For details see here: http://algs4.cs.princeton.edu/34hash/ You can select a simple hash function and handle collisions a simple way, for example by putting a collided value into the next available array slot.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.