Register and join over 40,000 other developers!
Recent Topics

Delete account
pindo  Jul 23 2020 01:33 AM

Print specific values from dictionary with a specific key name
Siten0308  Jun 20 2019 01:43 PM

Learn algorithms and programming concepts
johnnylo  Apr 23 2019 07:49 AM

Job Gig PHP Form Needed
PJohnson  Apr 18 2019 03:55 AM

How to make code run differently depending on the platform it is running on?
xarzu  Apr 05 2019 09:17 AM
Recent Blog Entries
Recent Status Updates
Popular Tags
 networking
 Managed C++
 stream
 console
 database
 authentication
 Visual Basic 4 / 5 / 6
 session
 Connection
 asp.net
 import
 syntax
 hardware
 html5
 array
 mysql
 java
 php
 c++
 string
 C#
 html
 loop
 timer
 jquery
 ajax
 javascript
 programming
 android
 css
 assembly
 c
 form
 vb.net
 xml
 linked list
 login
 encryption
 pseudocode
 calculator
 sql
 python
 setup
 help
 game
 combobox
 binary
 hello world
 grid
 innerHTML
[SOLVED]Determine all (i,j) pairs such that A[i] = A[j]
Started by restin84, Oct 15 2012 11:34 AM
algorithms
6 replies to this topic
#1
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.
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.
#2
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))
#3
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.
#4
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:
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.
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.
#5
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).
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).
Programming is a branch of mathematics.
My CodeCall Blog  My Personal Blog
My MineCraft server site: http://banishedwings.enjin.com/
#6
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)
#7
Posted 17 October 2012  05:48 AM
Sometimes the goal is to find a solution for "average data".
Programming is a branch of mathematics.
My CodeCall Blog  My Personal Blog
My MineCraft server site: http://banishedwings.enjin.com/
Also tagged with one or more of these keywords: algorithms
Language Forums →
C and C++ →
Tool for testing exactly the performance of program / algorithmStarted by AamirYousafi, 13 Aug 2016 performance, testing, tools and 1 more... 


General Forums →
General Programming →
[Excel 2003] Algorithms for a business worksheet!Started by Donovan, 17 May 2016 excel, expense sheet, algorithms and 1 more... 


Language Forums →
Java →
What is wrong with my merge sort implementation ?Started by Aemara, 05 Dec 2015 java, mergesort, algorithms 


Language Forums →
C and C++ →
KMP algorithm (text algorithm) printing outputStarted by givenup09, 20 Aug 2014 c++, textalgorithm, algorithms 


General Forums →
General Programming →
Asking for an Algorithm book recommendationStarted by NortonPredator, 19 Mar 2014 algorithms 

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