How to return an ArrayList of rows with a minimum number of occurrences?

Question

I have a String[] , originalStringArray in which there are duplicates. So, {"dog","cat","dog","fish","dog","cat"} .

I wanted to create a function that returns strings that happen exactly a specific number of times. For here, if I said 3, he would return the “dog”, but not the “cat”.

Here is my current code:

 public ArrayList<String> returnMultiples(String[] originalStringArray,int requiredCount){ ArrayList<Integer> mCount = new ArrayList<>(); List<String> list = Arrays.asList(originalStringArray); ArrayList<String> result = new ArrayList<>(); // Count occurrences in original string for(String item: originalStringArray){ mCount.add(Collections.frequency(list,item)); } // If frequency is equal to count, add to array list for(int i=0; i<mCount.size(); i++){ if(mCount.get(i) == requiredCount){ result.add(originalStringArray[i]); } } return result; } 

The problem is that I read somewhere that the Collections library is very slow and draggable, and it also seems that this method can be reduced using HashSets and tables. Unfortunately, I do not seem to understand how to do this. Is there a better way to do this?

Answer 1

This will require some kind of card. Here is an example written using HashMaps:

 public ArrayList<String> returnMultiples(String[] array, int min){ HashMap<String, Integer> counts = new HashMap<String, Integer>();//instantiate a new HashMap //loop through the array and count the occurrences of each different string in the array for(int i = 0; i < array.length; i++){ String word = array[i]; if(counts.containsKey(word)) counts.put(word, counts.get(word) + 1); else counts.put(word, 1); } ArrayList<String> multiples = new ArrayList<String>(); //check if any of the words occur >= min times. if so, add them to the returning list. for(String key : counts.keySet()){ if(counts.get(key) >= min){ multiples.add(key); } } return multiples;//return the list we just created of the desired strings } 

Depending on the length of the lines, a HashMap will be slightly more efficient than using collections, although the difference is mostly negligible.

Answer 2

You will need to use HashMap for this task.

Suppose your HashMap contains the number of occurrences of a given string, so it will be of type HasMap<String,Integer>

And now, lets you iterate over your collection:

• Get another row from your collection
• Check if pointer line exists in HashMap (#contains)
• If it does not exist, add a new element with a string key (hashMap.put (stringKey, 1);
• If it exists, put the element with the same key, but increase the internal counter (hashMap.put (stringKey, hashMap.get (stringKey) +1)
• Continue

Now your hashmap contains the exact number of occurrences of the given rows from your collections.

A quick search will be to create a reverse HashMap<Integer,String> , but there is a chance that the counters will be duplicated and this will not work. To get the string that appears in this string, you have to iterate over all the keys of the card and return only those that meet in accordance with your criteria.

Answer 3

Your algorithm will return duplicates.

A HashSet is part of the Collections library, so you are not profitable.

Your loop containing Collections.frequency is O (n ^ 2) algorithm. (for each row in originalStringArray Collections.frequency, the entire originalStringArray is repeated again).

You can only do this with a HashMap.

An increment of an integer in the map for each row in the original StringArray.

Delete all keys with a value other than required.

Add map.keySet () to the new ArrayList if you really intended to return an ArrayList.

or map.keySet (). toArray (String [map.size ()]) if you want an array.

Answer 4

You can use the AVL Tree , the premise would be that if you assumed that 1,000,000 elements were specified in your array, it would take 1,000,000 steps to go through this data structure. Using the AVL Tree will need to follow the O(Log (1,000,000)) steps, which are == 6 , are pretty neat. This would be a good approach if your data were dynamic, although you would have to optimize the inserts.

With the AVL tree, everything will be sorted, so you get O(Log N) time. Instead of looping through an array this way for N Steps :

You might have something like this:

Where he checks the root and sees that Char c is larger than the first Char in dog , and moves to the left. Essentially, 1/2 search time is reduced by each step, making step O(Log N) . You need to maintain a balanced tree height.

The good thing about AVL Tree is that your data is sorted all the time, since the tree needs to be balanced.

If the data doesn't change often and you don't need the sorted data, it's probably best to use a HashMap .

Answer 5

I believe it is fairly efficient to use hash maps.

The shortest code that comes to my mind (and which uses HashMaps) will look like this:

 String[] filter(String[] collection, int requirement) { final HashMap<String, Integer> temp = new HashMap<>(); for (String item : collection) { int current = temp.getOrDefault(item, 0); temp.put(item, ++current); } final Iterator<Entry<String, Integer>> iterator = temp.entrySet().iterator(); while (iterator.hasNext()) { final Entry<String, Integer> entry = iterator.next(); if (entry.getValue() != requirement) { iterator.remove(); } } return temp.keySet().toArray(new String[temp.size()]); } 

What can be used as follows:

 final String[] array = new String[]{ "dog", "dog", "dog", "cat", "cat", "fish", "cat" }; final String[] result = filter(array, 3); for (String item : result) { System.out.println(item); } 

And it generates output as expected:

cat

dog