Finding the intersection of elements in two sets Is there another better way to implement those two methods in 1 and 2?


  
  Implement the method contains.
  contains returns true if the given element
  is a member of the set, and false otherwise.
  Implement the method intersection.
  intersection returns a set which contains the elements
  in the set that are also members of the given set
  
  
  output:

{9, 1, 4, 3, 7, 5}

{4, 2, 8, 5, 7}

{4, 7, 5}





public class IntSet {

private int[] elements = null;

public IntSet(int[] elements) {
    this.elements = new int[elements.length];
    for (int pos = 0; pos &lt; elements.length; pos++) {
        this.elements[pos] = elements[pos];
    }
}


// toString returns a string representation of the set
public String toString() {
    String s = "{";
    if (elements.length == 0)
        s = s + "}";
    else {
        for (int pos = 0; pos &lt; elements.length - 1; pos++)
            s = s + elements[pos] + ", ";
        s = s + elements[elements.length - 1] + "}";
    }

    return s;
}

// contains returns true if the given element
// is a member of the set, and false otherwise.
public boolean contains(int element) {

    for (int i = 0; i &lt; this.elements.length; i++) {
        if (this.elements[i] == element)
            return true;
    }
    return false;
}


// intersection returns a set which contains the elements
// in the set that are also members of the given set
public IntSet intersection(IntSet set) {
    // use the method contains
    int members = 0;
    for (int i = 0; i &lt; elements.length; i++) {
        if (set.contains(elements[i]))
            members++;
    }

    int[] newMembers = new int[members];
    int position = 0;
    for (int i = 0; i &lt; elements.length; i++) {
        if (set.contains(elements[i]))
            newMembers[position++] = this.elements[i];

    }
    return new IntSet(newMembers);
}

//Some instances of the class IntSet are created and used like this:
public static void main(String[] args) {
    int[] numbers1 = {9, 1, 4, 3, 7, 5};
    IntSet set1 = new IntSet(numbers1);
    int[] numbers2 = {4, 2, 8, 5, 7};
    IntSet set2 = new IntSet(numbers2);
    System.out.println(set1);
    System.out.println(set2);

    IntSet set = set1.intersection(set2);
    System.out.println(set);
    //When this code fragment is executed, the following printout is produced:
    //{9, 1, 4, 3, 7, 5}
    //{4, 2, 8, 5, 7}
    //{4, 7, 5}
  }
}
Is there another better way to implement those two methods in 1 and 2?


Of course there is.

My advice is to think about the problem as though you were solving the problem without a computer.

Here, I'm going to give you a list of a thousand unsorted integers between 0 and 999999.

Now I'm going to ask you one thousand times whether a particular number I've chosen at random is on the list.

Would you really try to answer every question by reading down the list from top to bottom every time? 

Give some thought as to how you might solve that problem before you read on.

.

.

.

.

.

No, really, think about it.

.

.

.

You probably thought something like 


the first time I go down the list, I could make ten smaller lists:  numbers I've seen from 0-99999, numbers I've seen from 100000-199999, from 200000-299999, and so on.  That will take a thousand steps to make ten buckets of roughly 100 items each.
Then the second time I'm asked the question, I can first figure out what bucket the number might be in. Then I can search that bucket, and I know I will only have around 100 things to check instead of 1000.
And hey, while I'm doing that, I might as well divide that bucket up into ten buckets of roughly ten items each!


Every time you do a search that makes ten more buckets, you make subsequent searches that hit that bucket ten times faster.

All right, that should get you started; can you implement something like this bucketing algorithm in code?

Now, think the same way about intersection. Can you use the same bucketing trick to make intersection vastly faster? Or something similar?  Again, think about how you would solve the problem if I asked you to do it by hand.