I was solving this problem:- You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: J = "aA", S = "aAAbbbb" Output: 3 Example 2:
Input: J = "z", S = "ZZ" Output: 0
My logic for solution 1.
Hash the stones(unordered_map) so that we have the frequency of each type and have to find only the different stones in the given jewels once. The find function takes o(n) for each stone n hence the time complexity is O(n^2).
int numJewelsInStones(string j, string s) {
unordered_map<char, int>stones;
for(char s1:s)
++stones[s1];
auto it = stones.begin();
int count = 0;
for(it = stones.begin(); it != stones.end(); ++it)
{
char s1 = it->first;
if(j.find(s1) != string::npos)
count += it->second;
}
return count;
So i thought that o(n^2) was too much and decided to try to furthur optimise this. So i hashed the jewels as well by putting it into an unordered_set. That way, all duplicated are removed and it takes o(1) time to find a stone in it. So, for each stone it takes o(1) time and hence time complexity becomes o(n).
int numJewelsInStones(string j, string s) {
unordered_map<char, int>stones;
for(char s1:s)
++stones[s1];
unordered_set<char>uset(j.begin(), j.end());
auto it = stones.begin();
int count = 0;
for(it = stones.begin(); it != stones.end(); ++it)
{
char s1 = it->first;
if(uset.find(s1) != uset.end())
count += it->second;
}
return count;
The problem arises here- when i used the clock function from time.h to measure the run time
for solution 1 i got 0.000126 units of time
for solution 2 i got 0.000145 units of time
which does not makes sense when the first one is o(n^2) and the second one is o(n).
btw, this is my code for getting the time-
int main()
{
clock_t tStart = clock();
Solution ob;
string j = "aA", s = "aAAbbbb";
cout << ob.numJewelsInStones(j, s) << endl;
cout << (double)(clock() - tStart)/CLOCKS_PER_SEC;
cout << endl;
return 0;
}
Is anyone able to explain this anomaly to me?
Aucun commentaire:
Enregistrer un commentaire