Two arraylists
Hi guys,
I'm just unsure about this code that I've written for a problem. Please tell me what you think:
Question: You're given two Integer ArrayLists.
1. Write a method to return the intersection of these two lists.
2. Write a method to return the union of these two lists.
My work so far:
1.
public ArrayList<Integer> intersection(ArrayList<Integer> a, ArrayLIst<Integer> b)
{
ArrayList <Integer> result =new ArrayList <Integer> ();
for (int i = 0; i < a.size(); i++)
{
for (int k = 0; k < b.size(); k++)
{
if(a.get(i) == b.get(k))
result.add(a.get(i));
}
}
return result;
}
2.
Beginning is the same stuff as above.
boolean check;
result.add(a);
for (int i = 0; i < a.size(); i++)
{
check =true;
for (int k = 0; k < b.size(); k++)
{
if (a.get(i) == b.get(k))
check =false;
}
if (check)
result.add(a.get(i));
}
return result;
What do you guys think? For some reason, I feel like I'm unnecessarily complicating something, but I can't put my finger on it. Is this good enough or can I made this more compact and efficient somehow?
Thanks and bye.
[2186 byte] By [
p_sonya] at [2007-11-26 16:00:16]
Have you checked out the API for List or ArrayList? There may be some useful methods there.
Also, don't concepts like union and intersection make more sense with sets than lists?
Potential bug: do you the difference between
x ==y
//and...
x.equals(y)
Message was edited by:
DrLaszloJamf
> Also, don't concepts like union and intersection make> more sense with sets than lists?But that wasn't his assignment. ;-)
I didn't look really closely at your union logic - but it makes me uneasy. You could use a Set and add everything in both A and B to it. Then you can return new ArrayList(set).
Also, I wouldn't use '==' the way you are. Autoboxing will probably save you - but I'd suggest using .equals() instead, to make it clear that you're not trying to check for the same reference, but rather for content.
Does that help any?
G
Don't use "==". Use .equals. Two Integer objects with the same numeric value might not be ==, but they will definitely be .equals.
For intersection:
Can you use the "contains" method of ArrayList? That would be useful--you wouldn't need to explicitly use two loops (you'd use one, checking "contains" for each element; "contains" would use one loop itself, but that loop wouldn't show up in your code).
For union:
Can you use a Set<Integer> (e.g., a HashSet<Integer>)? That would make it really easy. If not, "contains" will help you here, too.
public class FunWithAutoBoxing {
public static void main(String... args) {
for(int i=0; i<150; i++)
test(i,i);
}
static void test(Integer a, Integer b) {
System.out.printf("%d == %d is %b%n", a, b, a==b);
}
}
> ...
> What do you guys think? For some reason, I feel like
> I'm unnecessarily complicating something, but I can't
> put my finger on it. Is this good enough or can I
> made this more compact and efficient somehow?
Try this (untested) code snippet:
List<Integer> intersection(List<Integer> a, List<Integer> b) {
Set<Integer> set = new HashSet<Integer>(a);
set.retainAll(b);
return new ArrayList<Integer>(set);
}
List<Integer> union(List<Integer> a, List<Integer> b) {
Set<Integer> set = new HashSet<Integer>(a);
set.addAll(b);
return new ArrayList<Integer>(set);
}
> > public class FunWithAutoBoxing {
>public static void main(String... args) {
>for(int i=0; i<150; i++)
> test(i,i);
>
>static void test(Integer a, Integer b) {
> System.out.printf("%d == %d is %b%n", a, b,
> a==b);
>}
>
I'm sure you know this, but the OP might not:
Even without autoboxing, he'll likely get "false" with "==". If he uses Integer.valueOf to create all of the Integers, he'll get autoboxing-like results. If he uses "new Integer" to create any of the Integers, he'll get false for all "==" comparisons that involve the Integers he created with the "new Integer" (unless he put the same reference in both lists, but that's unlikely).
If you have IntegerA == IntegerB, Java compares references, not values.
If you have intA == IntegerB (or IntegerA == intB), Java unboxes the Integer and compares values (it doesn't box the int and compare references).
> > > > public class FunWithAutoBoxing {
> >public static void main(String... args) {
> >for(int i=0; i<150; i++)
> > test(i,i);
> >
> >static void test(Integer a, Integer b) {
> > System.out.printf("%d == %d is %b%n", a, b,
> > a==b);
> >}
> >
>
> I'm sure you know this, but the OP might not:
[snip autoboxing and Integer pooling voodoo]
They don't call you the omnipotent one for nothing!
> > > > > > public class FunWithAutoBoxing {
> > >public static void main(String... args) {
> > >for(int i=0; i<150; i++)
> > > test(i,i);
> > >
> > >static void test(Integer a, Integer b) {
> > > System.out.printf("%d == %d is %b%n", a, b,
> > > a==b);
> > >}
> > >
> >
> > I'm sure you know this, but the OP might not:
>
> [snip autoboxing and Integer pooling voodoo]
>
> They don't call you the omnipotent one for nothing!
Thanks, but I didn't know anything offhand. I do have a Java 1.5 compiler available here, and ran a few tests (because I was curious).
Thanks for the responses, guys. I don't think we can use sets, since we haven't even started learning about them.
Doremi, I don't know much about contains, but is this how it works?
1.
public ArrayList<Integer> intersection(ArrayList<Integer> a, ArrayLIst<Integer> b)
{
ArrayList <Integer> result = new ArrayList <Integer> ();
for (int i = 0; i < a.size(); i++)
{
if (b.contains(a.get(i)))
result.add(a.get(i));
}
return result;
}
2.
Beginning is the same stuff as above.
result.add(b);
for (int i = 0; i < a.size(); i++)
{
if(!(b.contains(a.get(i))))
result.add(a.get(i));
}
return result;
Sorry if I've made any stupid errors :p, pretty new to java.
Thanks again.
> Thanks for the responses, guys. I don't think we can
> use sets, since we haven't even started learning
> about them.
>
> Doremi, I don't know much about contains, but is this how it works?
Yes, I think your #1 for intersection looks good (though I'd put { } around the statement that goes with "if" [not strictly necessary, but it makes it easier to read, and easier to add more statements controlled by the "if" later).
I think your #2 is close. But, I don't think it will compile (your original #2 wouldn't have, either). On the first line, you want to "addAll(b)", not "add(b)":
result.addAll(b);
In both of your methods, you'll get duplicate values in the result if they occurred twice in 'a' (for intersection) or twice in 'b' (for union). But, if 'a' doesn't duplicate any values within itself and 'b' doesn't duplicate any values within itself, your methods will give only unique values in the results.
