Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

[SOLVED]Determine all (i,j) pairs such that A[i] = A[j]

algorithms

  • Please log in to reply
6 replies to this topic

#1 restin84

restin84

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 88 posts
  • Programming Language:C, Java, C++
  • Learning:PHP, Python, Assembly

Posted 15 October 2012 - 11:34 AM

Hi guys. I've been thinking over a homework problem for awhile now. Most of the solutions I have considered are inefficient so I was hoping someone may be able to give me a hint(not a solution) as to which direction I should move in.

Given an array of n>=2 numbers(possibly repeated), determine all pairs of indices (i,j) such that A[i] = A[j]

I know I can just use a nested for loop but the running time is O(n^2). I'm thinking there should be a more efficient way to do it.
  • 0

#2 BIGboss29

BIGboss29

    CC Lurker

  • Just Joined
  • Pip
  • 2 posts
  • Programming Language:Java, C++
  • Learning:C, C#, PHP, Python, JavaScript, Ruby, PL/SQL, Lisp, Assembly

Posted 15 October 2012 - 01:13 PM

Maybe if you try to using a binary tree to store and compare elements in the array it would me much easier and faster. O(log(n))
  • 0

#3 RhymeTime

RhymeTime

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 65 posts
  • Location:Odenton, MD
  • Programming Language:C, PHP, Python, JavaScript, Assembly, Others
  • Learning:C, PHP, Python, JavaScript, Assembly, Others

Posted 15 October 2012 - 02:05 PM

I am assuming that it is not necessary that i = j++, in which case I don't think a binary tree is going to be much help. I don't think you can get any better than O(n^2) since you are forced to compare each element against every other element. To get anything less will imply that you are doing less than that many comparisons and then it would be possible that you have not found every pair in the array.
  • 0

#4 lethalwire

lethalwire

    while(false){ ... }

  • Senior Member
  • PipPipPipPipPipPip
  • 766 posts
  • Programming Language:C, Java, PHP, JavaScript
  • Learning:PHP

Posted 16 October 2012 - 11:44 AM

In the following way, I'm thinking you could acquire O(n), linear time:

The following assumes you know the maximum value of the numbers within the array and that they are integers.
With this method, you can use the indices of a secondary array to determine where to find duplicates.
So let's say you create a class Duplicate and you know the values in your array range from [0, 20,000) exclusive.
You can then create an array Duplicate duplicates[20,000].
So if your array contains the following [1, 2 1, 10, 15, 15, 0] then at position 0 of duplicates, you'll hold a list which contains 6. (Because the number zero is located at position 6).
Position 1 of duplicates would then hold a list that contains 0 and 2. (Because the number 1 is located at position 0 and 2)
Position 2 of duplicates would then hold a list that contains 1. (Because the number 2 is located at position 1)
...

Then the algorithm would look something like:
for( int i: i < array.length; i++ )
  duplicates[array[i]].addDuplicateIndex(i)

The obvious downside of this is algorithm is space requirements. But, if you know you've got a small range to work with, then this method could be feasible.
  • 1

#5 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 16 October 2012 - 12:15 PM

A way you could get O(n log(n)):
reload your array into a new array of pair values, where they are <old index, old value>. Then sort this array with a quick sort on the old value. Finally, loop through the sorted array printing pairs (theoretically O(n^2) if all are the same, but much lower in practice).
  • 1

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#6 restin84

restin84

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 88 posts
  • Programming Language:C, Java, C++
  • Learning:PHP, Python, Assembly

Posted 16 October 2012 - 12:34 PM

Okay. Thanks guys. I have to do an analysis also. I'm beginning to think the problem cannot be solved in any better than O(n^2) (worst case time that is)
  • 0

#7 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 17 October 2012 - 05:48 AM

Sometimes the goal is to find a solution for "average data".
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download