We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Data Structures
  3. Arrays
  4. Sparse Arrays
  5. Discussions

Sparse Arrays

  • dgodfrey + 7 comments

    You can use an unordered_multiset (C++11) and its count method to make this easier:

    #include <iostream>
#include <iterator>
#include <unordered_set>
using namespace std;

int main() {
    int n, q, i;
    string str;
    unordered_multiset<string> s;
    cin >> n;
    for (i = 0; i < n; ++i) {
        cin >> str;
        s.insert(str);
    }
    cin >> q;
    for (i = 0; i < q; ++i) {
        cin >> str;
        cout << s.count(str) << '\n';
    }
}
    • robotikid + 0 comments
      [deleted]
    • 15h61a1218 + 0 comments

      thanks for posting your code helped a lot

    • shahane_rohan96 + 0 comments

      Thanks!! That was very helpful!

    • M_G_B + 0 comments

      is there any simpler code rather than using some other library

    • [deleted] + 1 comment

      instead of using unordered_set, it would be quicker with set because unordered_set takes a constant O(1) while set takes O(log n)

      • ford_hash + 0 comments

        Are you actually trying to say that O(1) is slower than O(log n)?

        Wat.

    • pulkit_rathi17 + 1 comment

      We can also use map with almost similar implementation. Key is required string and value is the number of occurance of that string. If a key is not present in map , it's value is '0' by default.

      #include <string>
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string,int> m;
    int n,q;
    string s;
    cin>>n;
    
    for(int i=0; i<n; i++){
        cin>>s;
        m[s]++;
    }
    
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>s;
        cout<<m[s]<<endl;
    } 
    return 0;
}
      • yzkuris + 1 comment

        I used your approach, thank you for the post

        • akash_30_1995 + 0 comments

          Very helpful. Thanks Buddy.

    • david_daverio + 1 comment

      I dont understand one thing:

      unordered_set sould contain no duplicated elements, so count would return 0 or 1.... How to overcome this issue?

      http://www.cplusplus.com/reference/unordered_set/unordered_set/count/

      • ArshadAQ + 0 comments

        Thats why you have to use unordered_multiset