Saturday, March 8, 2014

LeeCode: remove duplicate VVV Using HashSet


Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Analyis:
The problem itself is not a big deal. At first shot, I used a HashSet to save nodes. Code is as follows

However it turns out to be wrong because of the misunderstanding of HashSet. contains() which calls equals() to compare. It works for primitive type. See the accepted code.

Actually it also works for String type. Here is the explanation from Oracle Documentation.

The equals() Method

The equals() method compares two objects for equality and returns true if they are equal. The equals() method provided in the Object class uses the identity operator (==) to determine whether two objects are equal. For primitive data types, this gives the correct result. For objects, however, it does not. The equals() method provided by Object tests whether the object references are equal—that is, if the objects compared are the exact same object.
To test whether two objects are equal in the sense of equivalency (containing the same information), you must override the equals() method. Here is an example of a Book class that overrides equals():
public class Book {
    ...
    public boolean equals(Object obj) {
        if (obj instanceof Book)
            return ISBN.equals((Book)obj.getISBN()); 
        else
            return false;
    }
}
Consider this code that tests two instances of the Book class for equality:
// Swing Tutorial, 2nd edition
Book firstBook  = new Book("0201914670");
Book secondBook = new Book("0201914670");
if (firstBook.equals(secondBook)) {
    System.out.println("objects are equal");
} else {
    System.out.println("objects are not equal");
}
This program displays objects are equal even though firstBook and secondBook reference two distinct objects. They are considered equal because the objects compared contain the same ISBN number.
You should always override the equals() method if the identity operator is not appropriate for your class.

Solution II
The list is sorted, so simply compare current node with previous node. Code:



Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
I solved this problem with two HashSet by extending the first problem. Delete in place is possible, but is kinda complicated. 


No comments:

Post a Comment