题解 | #牛牛的魔法卡#

思路：

题目的主要信息：

数轴上有n个点，每个点有自己的坐标和数值
从任意点出发，求经过K个不同数值点的最小花费

方法一：暴力法（超时）
具体做法：
对排序后的坐标点，每个点都可以作为一个区间的起点，我们遍历所有起点，往后遍历，找到后续区间是否有k个不同数值的点（使用哈希表，哈希表key值记录坐标上的数值，哈希表大小达到k即可），对于所有的区间，我们找到一个最小值即可。

class Solution {
public:
    static bool comp(vector<int>& a, vector<int>& b){ //重载比较
        return a[1] < b[1];
    }
    int solve(int n, int k, vector<vector<int> >& card) {
        sort(card.begin(), card.end(), comp); //按照坐标排序
        int res = INT_MAX;
        for(int i = 0; i < n; i++){ //每个点都可以作为区间起点
            unordered_map<int, int> mp;
            mp.clear();
            for(int j = i; j < n; j++){ //往后找k个不同的数值
                mp[card[j][0]]++; //记录不同的数值
                if(mp.size() == k){ //找到k个
                    res = min(res, card[j][1] - card[i][1]); //维护最小值
                    break; 
                }
            }
        }
        if(res == INT_MAX) //无法经过k个不同的点
            return -1;
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，两层循环，这是无序哈希表，可以直接访问删除，复杂度为 $O(1)$ ，排序的复杂度 $O(nlog_2n)$ 属于低次幂，舍去
空间复杂度： $O(k)$ ，哈希表最大长度为 $k$

方法二：排序+滑动窗口+哈希表
具体做法：
对所有点按照坐标排序，然后从坐标最前出发，使用哈希表维护不同的数值及这个数值的点的数量，维持一个窗口，当哈希表长度等于k时，窗口左端右移，并从哈希表中减少相应左边窗口值得数量，当数量为0时，从哈希表中删去这个值直到哈希表长度小于k。而窗口右端循环一次自然增长。
图片说明

class Solution {
public:
    static bool comp(vector<int>& a, vector<int>& b){ //重载比较
        return a[1] < b[1];
    }
    int solve(int n, int k, vector<vector<int> >& card) {
        sort(card.begin(), card.end(), comp); //按照坐标排序
        int res = INT_MAX;
        unordered_map<int, int> mp; //统计不同的数值
        for(int l = 0, r = 0; r < n; r++){ //维持窗口
            mp[card[r][0]]++;
            while(l < r && mp.size() == k){ //缩小区间
                res = min(res, card[r][1] - card[l][1]); //记录最小值
                mp[card[l][0]]--;
                if(mp[card[l][0]] == 0)
                    mp.erase(card[l][0]);
                l++;
            }
        }
        if(res == INT_MAX) //无法经过k个不同的点
            return -1;
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n)$ ，窗口左端最多增长到 $n$ ，因此内循环总共会有 $n$ 次，因此复杂度相当于 $O(2n)$ ，而与排序的 $O(nlog_2n)$ 比起来是低次幂，故舍去
空间复杂度： $O(k)$ ，哈希表长度最大为 $k$