Блог пользователя Betlista

Counting map
Автор Betlista, 13 лет назад, По-английски

Counting map is special map used for counting things — values in map are integers. In Java it could be (first type, the one for key, could be something else):

Map<String, Integer> map = new HashMap<String, Integer>();

When incrementing counts I'm using this code(using tricks with autoboxing):

String s = ...; // we have value
Integer cnt = map.get( s );
map.put( s, cnt == null ? 1 : ++cnt );

When decreasing count I'm using (in most cases decresing is not needed):

String s = ...; // we have value
int cnt = map.get( s );
if ( cnt == 1 ) map.remove( s );
else map.put( s, --cnt );

Problems where counting map could be helpful:

On the other hand there are other aproaches to solve same problems, for example when you need to count characters, more effective solution is char[], but maps are my favourite data structure 0:-), but ones in TopCoder SRM the performace was a big issue that caused that my solution failed in system test (TLE).

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Hello guys, if you do not like this blog entry I would like to know why, really ;-)

I know that it is quite simple. My rating is not high, but I think it could help to someone.

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Oh, it was nice, your tutorials are pretty much useful, I guess Codeforces should have an fixed place, to all Tutorials and Editorials;

    → Ответить
»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

It's also a good way to compress coordinates (did I express this term correctly?..)

If we need to compress an array A, than we can do that in three steps:

int A[N];
// ...blah-blah-blah, A is filled with some big numbers
map<int, int> M;

for (int i = 0; i < n; i++) 
    M[A[i]]; // 1. Creating a key A[i] in M
 
int pt = 0;
for (map<int, int>::iterator it = M.begin(); it != M.end(); it++) 
    it->second = pt++; // 2. Assigning unique value for each key keeping order in set of values

for (int i = 0; i < n; i++)
    A[i] = M[A[i]]; // 3. Compressing source array

That's good way because if we need to put points in some special cases, like they are ends of some segments, we can just call something like M[A[i] — 1], M[A[i]], M[A[i] + 1] instead of thinking what we should put as A[i], what as A[i] + 1 etc...

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi

Thanks for your tutorials. I generally using c++, I using Java (with IdeOne ) if I have to use BigInteger (but I feel I don't use BigIntegers in the natural way, I feel there definitions and usage hard, maybe it's my fault). So I would really happy if you write a tutorial about BigInteger or any area where Java know something that c++ don't. :)

→ Ответить