StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'd use an array rather than a hash map. If we're limited to ascii, that's just 256 entries; if we're using Unicode, 64k. Either way not an impossible size. Besides that, I don't see how you could improve on your approach. I'm trying to think of some clever trick to make it more efficient but I can't come up with any.</p> <p>Seems to me the answer is almost always going to be a whole list of characters: all of those that are used zero times.</p> <p><strong>Update</strong></p> <p>This is probably clost to the most efficient it could be in Java. For convenience, I'm assuming we're using plain Ascii.</p> <pre><code>public List<Character> rarest(String s) { int[] freq=new int[256]; for (int p=s.length()-1;p>=0;--p) { char c=s.charAt(p); if (c>255) throw new UnexpectedDataException("Wasn't expecting that"); ++freq[c]; } int min=Integer.MAX_VALUE; for (int x=freq.length-1;x>=0;--x) { // I'm assuming we don't want chars with frequency of zero if (freq[x]>0 && min>freq[x]) min=freq[x]; } List<Character> rares=new ArrayList<Character>(); for (int x=freq.length-1;x>=0;--x) { if (freq[x]==min) rares.add((char)x); } return rares; } </code></pre> <p>Any effort to keep the list sorted by frequency as you go is going to be way more inefficient, because it will have to re-sort every time you examine one character.</p> <p>Any attempt to sort the list of frequencies at all is going to be more inefficient, as sorting the whole list is clearly going to be slower than just picking the smallest value.</p> <p>Sorting the string and then counting is going to be slower because the sort will be more expensive than the count.</p> <p>Technically, it would be faster to create a simple array at the end rather than an ArrayList, but the ArrayList makes slightly more readable code.</p> <p>There may be a way to do it faster, but I suspect this is close to the optimum solution. I'd certainly be interested to see if someone has a better idea.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload