1

I am trying to find the number of Strings that only appear exactly once in an ArrayList.

How many I achieve this (preferably with the best possible time complexity)?

Below is my method:

  public static int countNonRepeats(WordStream words) {

    ArrayList<String> list = new ArrayList<String>();
    for (String i : words) {
      list.add(i);
    }

    Collections.sort(list);

    for (int i = 1; i < list.size(); i++) {
      if (list.get(i).equals(list.get(i - 1))) {
        list.remove(list.get(i));
        list.remove(list.get(i - 1));
      }
    }

    System.out.println(list);

    return list.size();
  }

Why doesn't it remove the String at list.get(i) and list.get(i-1)?

Improve this question
5
  • 1
    @FedericoPeraltaSchaffner do you have any ideas? :) Commented Mar 14, 2016 at 19:14
  • 1
    you would get concurrent modification exception for the above method. Commented Mar 14, 2016 at 19:19
  • @RahulSharma Not quite, concurrent modification exception is thrown from Iterator which is created mostly via for-each, not simple for(i..). But we may risk getting error because of wrong indexes. Commented Mar 14, 2016 at 19:20
  • Sorry, It doesn't. But I tried to run the code and it works like a charm. @Iona do you get any errors? Commented Mar 14, 2016 at 19:29
  • If you use Collections.sort the time complexity is O(n log n), but you can easily find the number of strings that appear exactly once in O(n) time using HashSets (but no sorting). Commented Mar 14, 2016 at 19:31

4 Answers 4

Reset to default
4

There is no need for sorting. A better approach would be to use two HashSet One for maintaining repeating and one for non-repeating words. Since HashSet internally uses HashMap, Ideally contains, get, put operation has o(1) complexity. So the overall complexity of this approach would be o(n). 

    public static int countNonRepeats(List<String> words) {

    Set<String> nonRepeating = new HashSet<String>();
    Set<String> repeating = new HashSet<String>();


    for (String i : words) {
        if(!repeating.contains(i)) {
            if(nonRepeating.contains(i)){
                repeating.add(i);
                nonRepeating.remove(i);
            }else {
                nonRepeating.add(i);
            }
        }
    }

    System.out.println(nonRepeating.size());

    return nonRepeating.size();
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

Here's one simple suggestion:

  1. First, sort your array by alphanumerical order
  2. Iterate through with a loop, if( !list.get(i).equals(list.get(i+1)) ) → unique
  3. If you find duplicates, increment i until you reach a different string

This will have the complexity of the sorting algorithm, since step 2+3 should be O(n)

Improve this answer

7 Comments

that won't work because e.g. [apple, apple, banana, banana] will return 1 instead of 0 because apple != banana
No because that's what step 3 avoids! read more carefully. In this example, "apple" is a duplicate at i = 0, so you iterate until !list.get(i).equals("apple") → i = 2 in the next cycle
ok you are correct! thank you sir! :) I'll upvote in 10 seconds
@Iona How many I achieve this (preferably with the best possible time complexity) Actually you don't even have to iterate it again. If you are using a HashSet then you can do it while scanning the words itself.
No need of sorting , please see my answer for better time complexity.
|
2

Is there any specific need of using an ArrayList? You can do it easily by using a HashSet.

Here is the code snippet:

public static void main (String[] args) {
    String[] words = {"foo","bar","foo","fo","of","bar","of","ba","of","ab"};
    Set<String> set = new HashSet<>();
    Set<String> common = new HashSet<>();
    for (String i : words) {
        if(!set.add(i)) {
            common.add(i);
        }
    }

    System.out.println(set.size() - common.size());
}

Output:

3

Here is the modified code:

public static int countNonRepeats(WordStream words) {
    Set<String> set = new HashSet<>();
    Set<String> common = new HashSet<>();
    for (String i : words) {
        if(!set.add(i)) {
            common.add(i);
        }
    }

    return (set.size() - common.size());
}
Improve this answer

2 Comments

You beat me to it! You can make it slightly more efficient by doing if (!set.add(i)) common.add(i);
@PaulBoddington Gotcha! :) Thanks for the valuable suggestion.
0

You can use hashmap to achieve this.With this approach we can count the occurrence of all the words,
If we are interested in only unique words then access the element having count = 1.
HashMap<String,Integer> - key represents the String from arraylist and Integer represents the count of occurrence.

        ArrayList<String> list = new ArrayList<String>();
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>();

        for (int i = 0; i < list.size(); i++) {

            String key = list.get(i);

            if (hashMap.get(key) != null) {
                int value = hashMap.get(key);
                value++;
                hashMap.put(key, value);
            } else {
                    hashMap.put(key, 1);
            }

        }
        int uniqueCount = 0;
        Iterator it = hashMap.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            if ((int) pair.getValue() == 1)
                uniqueCount++;
        }
        System.out.println(uniqueCount);
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.