• Post Reply Bookmark Topic Watch Topic
  • New Topic

Find common elements in collection  RSS feed

 
Karen Byk
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, long time listener, first time caller. I've been at this for some time and seem to be getting no where. I need to create an algorithm that finds the common element(s) in all arrays that has a signature of that has an efficiency of at most O(knlogn), uses a query array, and accepts as input a collection of arrays. I am aware my time would be better spent learning how to use array lists and hash sets, but I am supposed to use concepts already covered, and these have not been.
I feel like this code should work, but it is returning null for the array of common elements. Which means it obviously is not working correctly. I am hoping someone can help point me in the correct direction. I am also likely going to need hep implementing the sort algorithm, but I wanted to get the part of finding the common elements set first.



Thank you for your time and input
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to (posting on) JavaRanch, then

First off, I assume you mean "CommonElements", not "CommonElements2", in line 1.

The reason the array contains nulls if not all elements are present in both arrays is that the array is pre-sized to the size of the query array. It seems to work fine for the example you posted, but if collections[1] contains 3,7,11 instead, the last element is null because it is not contained in the query array. So it looks to me like it is working fine.

You could fix that by keeping track of how many elements are identical, and then creating a new array of that size at the end of the findCommonElements method and passing that back as a result.
 
Karen Byk
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was working on several different versions- didn't want to lose what I did, but I needed a fresh start. So I actually should have changed the other references to CommonElements2.
I did find a way to change the size to only valid elements... well created a new array for that. However, if I have 3 arrays it pulls the common elements from each comparison and doesn't pull the common elements from all 3 only. For example if I have:
{3, 7, 8,12, 38}
{3, 6, 7, 38, 40, 41}
{7, 38, 92}
It would give the result of {3, 7, 7, 38, 38} when it should be {7, 38}. I stared at this code for hours and don't see where to make that adjustment- would it be in the binarySearch method or the findCommonElements method?
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!