[数据结构与算法]力扣(LeetCode)1773. 统计匹配检索规则的物品数量(C++)

一、环境说明

1. 本文是 LeetCode1773. 统计匹配检索规则的物品数量。
2. 模拟。
3. 测试环境:Visual Studio 2019。

二、思路分析

直接匹配

朴素的思维模式是一次遍历：
简单匹配一下，$ruleKey$和$items$的规则，规则匹配，再匹配属性。

hash表

直观的简化做法是hash思想：
建立一个$hashmap$，把$ruleKey$映射为$item$对应属性的下标。题目给出$items[i]=[typei,colori,namei]$，我们要做的，就是把$type、color、name$依次映射为$0,1,2$。这一步帮我们省略了规则匹配，接下来只用匹配属性即可。

三、代码展示

直接匹配:

// 类型type 颜色color 名称name
class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        int ans = 0;
        for(int i =0;i<items.size();i++){
            if("color"==ruleKey){
                if(items[i][1]==ruleValue){
                    ans++;
                }//物品颜色
            }else if("type"==ruleKey){
                if(items[i][0]==ruleValue){
                    ans++;
                }
            }else{//name
                if(items[i][2]==ruleValue){
                    ans++;
                }
            }
        }
        return ans;
    }
};

哈希表:

class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        unordered_map<string,int> hash = {{"type",0},{"color",1},{"name",2}};
        int ans = 0,index = hash[ruleKey];
        for(auto x:items){
            if(x[index] == ruleValue) ans++;
        }
        return ans;
    }
};

四、博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:$O(n)$ ,$n$是物品数量。直接匹配和哈希表，都只进行一次遍历。时间复杂度是$O(n)$。
2. 空间复杂度:$O(1)$,除了若干变量使用的常量空间，没有使用额外的线性空间。特别的，本题$hash$表也是常量级空间$|C|=3$。