Suppose I have the following code fragment:
for(int i=0; i < n.length(); i++) {
int aux = n[i];
if(map.containsKey(aux)) {
map.put(aux, map.get(aux)+1);
} else {
map.put(aux, 1);
}
}
My map is a HashMap. I know the for would be O(n) then map operations have O(1), however I have three map operations there (containsKey, put and get) so would that be O(3n) or still O(n)?? And why?
O(3N) and O(N) would be just considered O(N).
I guess, maybe getOrDefault()
would be an option, if I'd correctly recall:
for (int i = 0; i < n.length(); i++) {
int aux = n[i];
map.put(aux, map.getOrDefault(aux, 0) + 1);
}
and your time and memory complexity would be both O(N).
I think another more readable version would be:
for (int i = 0; i < n.length(); i++) {
int aux = n[i];
map.put(aux, -~map.getOrDefault(aux, 0));
}
-~x
is just a bitwise operation for x + 1
(-~x = x + 1
). However, you can use whichever you would be comfortable.