Overclock.net banner

1 - 10 of 10 Posts

·
Registered
Joined
·
409 Posts
Discussion Starter #1
Well I am almost done with an very simple program I wrote for my Programming 1 class however I am completely at a wall when it comes to this step. After the user inputs a string(got that part
biggrin.gif
) I need to make it so the user gets an option to 'decipher' the string, sorting the occurrence of every letter in descending order. For example if the string is "aa bbb c" the output is "B ,A , C".

I havent the slightest on how to approach this. So far I was able to store the occurrence of each letter in an integer array count[0-25], and can sort it using array.sort, however I think that is a deadend for I don't know how to distinguish for example count[2](this will be C) with count[0] (A) for they are just numbers.
 

·
Registered
Joined
·
817 Posts
you need a way to associate each letter with the number of occurrences. i believe the best way to do that is to use a TreeMap. There might be an easier way, but i like treemaps because they sort it for you. in this case, to sort based on the values, you will need to provide it a custom comparator.

1. set up a custom comparator that sorts based on value.
2. pass the comparator to the treemap constructor
3. add key/values to the treemap

Code:

Code:
     // if the map doesn't have an entry for B
     if(!map.containsKey("B")){
          map.put("B", 1);
     }
     // if the map has an entry for B, get its current value and increment it
     else{
          map.put("B", map.get("B")+1);
     }
4. iterate through the treemap and print the keys in order.

a very good explanation with an example implementation can be found at http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java

the example uses a hashmap, but i think you can skip that part. the only thing you really need to change is that they use double for the value, but you probably want to use int.
 

·
Registered
Joined
·
409 Posts
Discussion Starter #3
Can you think of an alternative method for this possibly, for my class never gone over anything involving maps. I think it would be odd if I have that in my code.
 

·
Registered
Joined
·
817 Posts
sure. you could use an array 0-25 like you are doing. instead of counting with numbers though, store the actual letters in the array. just concatenate the letters. you can then sort based on the length of the strings inside each array location.

Code:

Code:
// i think this will work 
array[1] += "B";
for example, if array[0] contains "AA", then the letter 'A' occurred twice. "BBBB" would indicate 'B' occurred 4 times.
 

·
Registered
Joined
·
49 Posts
If the input is lowercase you can convert letter to hex then subtract 61 and that will give you the place in the array to increase count. Then you can sort into a 2nd array this time storing the letters. So if array[2] has the highest count you will want to do array2[0] = (2 + 61) char. If array[9] has the 2nd highest count you will want to do array2[1] = (9 + 61) char.
 

·
Software Developer
Joined
·
7,231 Posts
You need to use some built in methods for String in Java.

Source: http://docs.oracle.com/javase/6/docs/api/java/lang/String.html

Namely:

String.charAt(int);

In Java 1.7 u 4

You can use a switch statement for both characters and strings if (you need whole worlds).

//An int Array with 26 rows, each element representing a letter.

int[] characterCount = new int[26];

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

{

char temp = yourString.charAt(i);

switch (temp)

{

case 'a' :
{

characterCount[0] += 1;

break;
}
}

}

It is easier to do this with a HashMap or LinkedHashMap, but I figured you have to do it something like this. All you need now is a method that goes through the array finds the max number, get that index, that index translates to a character, like index 0 = a, or index 5 = f.

You then have to start search again and this time ignore the old max number, but look for the new max. You can do this with something like this pseudo code:

public String findMax(characterCount)

{

String solution = "";

int oldMax = 0;

int currentMax = 0;

int maxIndex = 0;

int count = 0;

while(count <= characterCount.length)

{

Go through each time, comparing to oldMax. When finished,

currentMax's index is saved and sent to below switch to converted

to letter, then you go back in with a new oldMax that matched the

last currentMax value. You want to make sure that you are less than

or equal to oldMax value, and repeat till you have reached a total number

of the array, and account for size 0 so you don't print characters that are 0.

switch (maxIndex)
{

each index accounts for a letter, if count is 0

then you:

solution += "A"

}
}

}

return Solution;

}

You can't just use Array Sort because then the data is meaningless, due to it being only useful in order. Its up to you to find the maxes yourself.
 

·
Registered
Joined
·
409 Posts
Discussion Starter #7
Quote:
Originally Posted by travesty View Post

sure. you could use an array 0-25 like you are doing. instead of counting with numbers though, store the actual letters in the array. just concatenate the letters. you can then sort based on the length of the strings inside each array location.

Code:

Code:
// i think this will work 
array[1] += "B";
I ended up going this route however don't know I how I can sort the string array. I really want to avoid using the comparator class.
 

·
Registered
Joined
·
817 Posts
Quote:
Originally Posted by OPENbracket View Post

I ended up going this route however don't know I how I can sort the string array. I really want to avoid using the comparator class.
try using a simple bubble sort. the performance isn't great but it's easy to implement.

here's some pseudocode from wikipedia that i modified slightly. the idea is that the while loop keeps going until no swapping occurs inside the for loop. that way we know that the array is in the correct order.

Code:

Code:
procedure bubbleSort( A : array of sortable items )
  repeat     // in java this would be a while loop
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i-1].length() > A[i].length() then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure
 

·
Registered
Joined
·
409 Posts
Discussion Starter #9
Quote:
Originally Posted by travesty View Post

try using a simple bubble sort. the performance isn't great but it's easy to implement.
here's some pseudocode from wikipedia that i modified slightly. the idea is that the while loop keeps going until no swapping occurs inside the for loop. that way we know that the array is in the correct order.

Thanks a bunch, it's alive!
 
1 - 10 of 10 Posts
Top