Count occurrences of elements inside array? (Java)

Question

I have been working on trying to figure out this algorithm for about 6 hours now and can't seem to come up with a solution. I am trying to count the occurrences of elements inside an array and may two more separate arrays. One for the unique instances, and one for how many times these instances occurs. I found some other thinks on here about array lists and hashMaps, but I am only able to use arrays.

For example, I have this array (already sorted):

{cats, cats, cats, dog, dog, fish}

I am trying to get make an array for the instances, so:

{cats, dog, fish}

And finally, how many times these instances occur:

{3, 2, 1}

Here is the code i have so far:

public void findArrs( String[] words )
{
  int counter = 1;
  for(int i = 0; i < words.length - 1; i++){
  if(!(words[i].equals(words[i+1]))){
  counter++; 
  }
 }

 String[] unique = new String[counter];
 int[] times = new int[counter];

 for(int i = 0; i < words.length; i++){

   }    
}

This is all the code I have after all my attempts.

Solution 1

This is how it could be done using only arrays. The tricky part is you must know the number of items before the array is created. So I had to create my own function to create a bigger array. Actually two, one for the count and one for the unique values.

If you can use Vectors you will be better off. Here is it without vetors:

public class HelloWorld{

     public static void main(String []args){
        String[] initalArray;

        // allocates memory for 10 integers
        initalArray = new String[6];
        initalArray[0] = "cats";
        initalArray[1] = "cats";
        initalArray[2] = "cats";
        initalArray[3] = "dog";
        initalArray[4] = "dog";
        initalArray[5] = "fish";

        String[] uniqueValues = new String[0];
        int[] countValues = new int[0];
        for(int i = 0; i < initalArray.length; i++)
        {
            boolean isNewValue = true;
            for (int j = 0; j < uniqueValues.length; j++)
            {
                if (uniqueValues[j] == initalArray[i])
                {
                    isNewValue = false;
                    countValues[j]++;
                }
            }

            if (isNewValue)
            {
                // We have a new value!
                uniqueValues = addToArrayString(uniqueValues, initalArray[i]);
                countValues = addToArrayInt(countValues, 1);
            }
        }

        System.out.println("Results:");
        for(int i = 0; i < countValues.length; i++)
        {
            System.out.println(uniqueValues[i] + "=" +  countValues[i]);
        }
     }

     public static String[] addToArrayString(String[] initalArray, String newValue)
     {
         String[] returnArray = new String[initalArray.length+1];
         for(int i = 0; i < initalArray.length; i++)
         {
             returnArray[i] = initalArray[i];
         }
         returnArray[returnArray.length-1] = newValue;

         return returnArray;
     }

     public static int[] addToArrayInt(int[] initalArray, int newValue)
     {
         int[] returnArray = new int[initalArray.length+1];
         for(int i = 0; i < initalArray.length; i++)
         {
             returnArray[i] = initalArray[i];
         }
         returnArray[returnArray.length-1] = newValue;

         return returnArray;
     }
}

As mentioned in the comments, if we know the array is in order, then we don't need to search through the entire previous array and can just check uniqueValues directly.

public class HelloWorld{

     public static void main(String []args){
        String[] initalArray;

        // allocates memory for 10 integers
        initalArray = new String[6];
        initalArray[0] = "cats";
        initalArray[1] = "cats";
        initalArray[2] = "cats";
        initalArray[3] = "dog";
        initalArray[4] = "dog";
        initalArray[5] = "fish";

        String[] uniqueValues = new String[0];
        int[] countValues = new int[0];
        for(int i = 0; i < initalArray.length; i++)
        {
            boolean isNewValue = true;
            if (i > 0)
            {
                if (uniqueValues[uniqueValues.length-1] == initalArray[i])
                {
                    isNewValue = false;
                    countValues[uniqueValues.length-1]++;
                }
            }

            if (isNewValue)
            {
                // We have a new value!
                uniqueValues = addToArrayString(uniqueValues, initalArray[i]);
                countValues = addToArrayInt(countValues, 1);
            }
        }

        System.out.println("Results:");
        for(int i = 0; i < countValues.length; i++)
        {
            System.out.println(uniqueValues[i] + "=" +  countValues[i]);
        }
     }

     public static String[] addToArrayString(String[] initalArray, String newValue)
     {
         String[] returnArray = new String[initalArray.length+1];
         for(int i = 0; i < initalArray.length; i++)
         {
             returnArray[i] = initalArray[i];
         }
         returnArray[returnArray.length-1] = newValue;

         return returnArray;
     }

     public static int[] addToArrayInt(int[] initalArray, int newValue)
     {
         int[] returnArray = new int[initalArray.length+1];
         for(int i = 0; i < initalArray.length; i++)
         {
             returnArray[i] = initalArray[i];
         }
         returnArray[returnArray.length-1] = newValue;

         return returnArray;
     }
}

Solution 2

Assuming that the words array has at least one element:

int numberOfDifferentWords = 1;
String firstWord = words[0];
for(int i = 0; i < words.length; i++) {
    if(!firstWord.equals(words[i])) {
        numberOfDifferentWords++;
    }
}

// These two arrays will contain the results. 
String[] wordResultArray = new String[numberOfDiffentWords];
int[] countResultArray = new int[numberOfDiffentWords];

// This will mark where we should put the next result
int resultArrayIndex = 0;

String currentWord = firstWord;
int currentWordCount = 0;
for(int i = 0; i < words.length; i++) {
    //if we're still on the same word, increment the current word counter
    if(currentWord.equals(words[i])) {
        currentWordCount++;
    }
    //otherwise, transition to a new word
    else {
        wordResultArray[resultArrayIndex] = currentWord;
        wordCountArray[resultArrayIndex] = currentWordCount;
        resultArrayIndex++;

        currentWord = words[i];
        currentWordCount = 1;
    }
}

As other answers have mentioned, this problem could be simplified by using a List such an ArrayList to store the results.

Solution 3

Make unique, times as instance variable so that you can retrieve them from another class using getter methods.

Note: Modified code can be found through comments (for line "Added line". for block between "Added code starts here" to "Added code ends here"). I tried to explain the implementation in code. Please let me know through comments if I need to work more on my documentation skills

public class someClass(){
  private String[] unique;
  private int[] times;
  //Added code starts here
  public String[] getUnique(){
    return this.unique;
  }

  public int[] getTimes(){
    return this.times;
  }
  //Added code ends here
  //Below implementation would work as intended only when words array is sorted
  public void findArrs( String[] words ) 
  {
    int counter = 1;
    for(int i = 0; i < words.length - 1; i++){
        if(!(words[i].equals(words[i+1]))){
            counter++; 
        }
    }

    unique = new String[counter];
    times = new int[counter];
    //Added line.
    unique[0] = words[0];  
    for(int i=0,j=0; i < words.length&&j < counter; i++){
   //Added code starts here
       if(!(unique[j].equals(words[i]))){
            j++; //increment count when latest element in unique array is not equal to latest element in words array
            unique[j] = words[i]; //add newly found unique word from words array to unique array
            times[j] = 1; //make the count to 1 for first non repeated unique word

        }
        else{

            times[j]++; //increment the count every time the string repeats
        }
   //Added code ends here
   }    
  }
}

Solution 4

You can achieve it using TreeMap:

public class NumberOfOccurences {

    public static void main(String[] args) {
        String[] testArr = {"cats", "cats", "cats", "dog", "dog", "fish"};
        String output = countNumberOfChild(testArr);

        System.out.println(output);

    }


    public static String countNumberOfChild(String[] list){
        Arrays.sort(list);

        TreeMap<String,Integer> noOfOccurences = new TreeMap<String,Integer>();


        for(int i=0;i<list.length;i++){
            if(noOfOccurences.containsKey(list[i])){
                noOfOccurences.put(list[i], noOfOccurences.get(list[i])+1);
            }
            else{
                noOfOccurences.put(list[i], 1);
            }
        }

        String outputString = null;
        while(!noOfOccurences.isEmpty()){
            String key = noOfOccurences.firstKey();
            Integer value = noOfOccurences.firstEntry().getValue();
            if(outputString==null){
                outputString = key+"="+value;
            }
            else{
                outputString = outputString + ";" + key+"="+value;
            }
            noOfOccurences.remove(key);
        }

        return outputString;
    }
}

View more solutions

Comments

[helloMundo]

I'm coding in java not javascript. Thanks though

[Pierre]

I'm Sorry :) But maybe this can give you an idea of what you can do

[helloMundo]

Yeah. I'm very new to java, new to coding actually, so most other codes and stuff are hard for me to break down.

[Pierre]

If it is possible for you to use ArrayLists in your java, this can also be done in a simple way

[Pierre]

You can use List<String>() and just add as you want, after you can call stringlist.toArray()

[ansible]

Yeah, but in a comment the OP said "I can only use arrays and loops", so I only used arrays and loops in my answer, but suggested they look at Vectors instead, Lists<String> would probably be better though (it's been a while since I programmed in java - generics didn't exist back then).

[mrjink]

The code doesn't (ab)use the property that the input array is sorted. ;)

[helloMundo]

This code looks good so far. But what is we wanted to constrain the wordResultArray and countResultArray to the occurrences. Like the example above, its started with array length 6 but it needs to be array length 3.

[ansible]

@mrjink - Good catch! Added a version with the assumption the array is sorted. Could also get the count more easily of unique values, but I leave that as an exercise to the reader... it's late :)

[martiansnoop]

Just added a block of code in the beginning to address this. It does involve iterating through the words array an additional time, though.

[helloMundo]

Sorry I was looking over your code again. Can you explain why there is the currentWord = words[i]; currentWordCount = 1; at the end of the for loop? Also if you have a if inside the for. Does is hop out of the if statement after their condition is met then goes to the for loop then restart?

[martiansnoop]

The code "currentWord = words[i]; currentWordCount = 1; " is encountered whenever we transition to a new word in the original array -- when the current word (words[i]) has transitioned from "cats" to "dog", for example. It's saving off "cats" and "3" in the result arrays, and then setting the current word to "dog" and "1" because this is the first "dog" that has been counted.

[martiansnoop]

Your second question pertains to a section that has changed (you can view the old version here: stackoverflow.com/posts/21229050/revisions). The if inside the for loop is intended to run one time -- the for loop would run until it found an element of the array that hadn't been populated. Once I find a null array index, I assign values to it and then use the "break" keyword which basically says "take the nearest for loop and stop iterating through it".

[martiansnoop]

I took that part off, though, because it isn't necessary to loop through the result arrays every time -- we can just keep track of the index where we intend to insert the next result (starting at 0 and incrementing each time we save a result)