• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Rob Spoor
  • Devaka Cooray
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Jj Roberts
  • Al Hobbs
  • Piet Souris

Find common elements in collection

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Rancher
Posts: 43027
76
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic