Java ArrayList remove dupes without sets [closed]

Question

I'm having problems removing duplicates from an ArrayList. It's for an assignment for college. Here's the code I have already:

public int numberOfDiffWords() {
    ArrayList<String> list = new ArrayList<>();
    for(int i=0; i<words.size()-1; i++) {
        for(int j=i+1; j<words.size(); j++) {
            if(words.get(i).equals(words.get(j))) {
                // do nothing
            }
            else  {
                list.add(words.get(i));
            }
        }
    }
    return list.size();
}

The problem is in the numberOfDiffWords() method. The populate list method is working correctly, as my instructor has given me a sample string (containing 4465 words) to analyse - printing words.size() gives the correct result.

I want to return the size of the new ArrayList with all duplicates removed.

words is an ArrayList class attribute.

UPDATE: I should have mentioned I'm only allowed to use dynamic indexed-based storage for this part of the assignment, which means no hash-based storage.

Answer 1

Since this is an assignment, I'm not going to write code. However, I'd suggest a different approach.

• iterate through the array as you are doing
• use the subList() method to construct a view of the array from the start up to but not including the current element
• use contains() to test whether the current element is in the sublist constructed in the previous step
• just count how many elements are found that are not contained in the prefix

My recommended approach should result in much simpler and easier-to-understand code. Note that all this is an O(n²) solution (as is yours, if you were to get it right).

Another approach, if modifying the array is allowed by the assignment, is to sort the array. Then equal elements will be adjacent and it is easy to count how many are unique. This is an O(n log(n)) approach. (You can also just make a copy of the array, which won't change the assymptotic complexity, but will slow down the solution.)

You won't get better than that without using a hashing function of some kind (HashSet or HashMap).