d0uch3b4g's blog

Help Post
By d0uch3b4g, history, 7 years ago, In English

Is there any efficient way to count occurrences of elements while taking input in an array (without using STL, Nested Loop)?? If so, then what's that process and what will be the complexity??

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If elements of array have  ≤ 107 upper bound, so you can use array to count them. If they can be big numbers, I don't think there is better way than map (or unordered_map). Complexity will be O(1) while using array, O(logN) otherwise.

int cnt[10000000]; // declare this as global to prevent memory overflow.
for (int i = 1; i <= n; i++) {
    cin >> arr[i]; cnt[arr[i]]++;
}
→ Reply