题解 | #牛牛的魔法卡#

牛牛的魔法卡

http://www.nowcoder.com/practice/9b6fe52a68904c77aa81502f57ceac86

题意整理：

题目给出n个坐标可能重复的点，每个点都带有一个数值，两个点之间的距离既为其坐标间的差值，要求求出从任意点出发，经过k个不同数值点的最小开销。

方法一：排序+枚举起点（超时）

核心思想：

很容易想到的一个思路就是枚举起点然后向后遍历到满足k个不同的数值点。首先将点按其坐标进行排序，然后将依次枚举每个点作为起点，向后遍历直到满足k个不同数值的点，然后更新答案。当存在一个点遍历到最后仍然无法满足k个不同数值时，可以结束枚举，因为后续的点更不可能满足k个不同数值对于k个不同数值的判断，可以采用哈希表 $O (1)$ 实现，既C++中的unordered_set即可。

核心代码：

class Solution {
public:
    int solve(int n, int k, vector<vector<int> >& card) {
        //按坐标排序
        sort(card.begin(), card.end(), [&](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });
        int ans = INT_MAX;
        for(int i = 0; i < n; ++i) {
            //枚举起点
            unordered_set<int> st;//统计不同的数值点
            int j = i + 1, dist = 0;
            st.insert(card[i][0]);
            while(st.size() < k && j < n) {//向后寻找
                dist += (card[j][1] - card[j - 1][1]);
                st.insert(card[j++][0]);
            }
            if(st.size() < k) break;//此时此点后面所有点都不可能作为成功的起点
            ans = min(ans, dist);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ 。排序开销为 $O (n l o g n)$ ,二重枚举开销为 $O (n^{2})$ ,总开销为 $O (n^{2})$ 。

空间复杂度： $O (k)$ ,即为哈希表的开销。

方法二：排序+滑动窗口

核心思想：

方法一超时的原因在于其对于每一个可能的区间(既枚举起点然后遍历得到终点所得区间)中的所有点都需要访问一次进行记录，对两个相邻区间，即使其除了两端外其他点都相同，也没有利用起来。而实际上区间在移动时，只需要去除尾部的点，加入头部的点即可，所以可以采用滑动窗口的方法加以优化。具体的说，在每一次区间迭代时，令右窗口不断右移直到满足区间内存在k个不同数值的点，然后左窗口在保证右移后区间内仍然有k个不同数值的点(既左窗口当前值在区间内的其他地方也有出现)的情况下不断右移。左窗口收缩结束后，记录本窗口长度，然后左窗口再次右移使得区间内剩余的不同数值的点不足k个(因为此时左窗口的值必为临界值，右移后有一个数值不再存在于区间内)，进行下一轮的区间迭代。在右窗口无法继续右移时，迭代结束。

alt

核心代码：

class Solution {
public:
    int solve(int n, int k, vector<vector<int> >& card) {
        //按坐标排序
        sort(card.begin(), card.end(), [&](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });
        int ans = INT_MAX;
        int left = 0, right = 0;
        unordered_map<int, int> mp;//记录区间内数值出现次数
        while(right < n) {
            while(right < n && mp.size() < k) {
                //右窗口扩大直到满足k个不同数值
                mp[card[right++][0]]++;
            }
            if(right == n && mp.size() < k) {
                //此时区间已经不可能做到k个不同数值，结束
                break;
            }
            while(mp[card[left][0]] > 1) {
                //左窗口缩小到仍能满足k个不同数值极限值
                --mp[card[left++][0]];
            }
            ans = min(ans, card[right - 1][1] - card[left][1]);
            mp.erase(card[left++][0]);//左窗口滑动，此时必不满足k个最大值
        }
        return ans == INT_MAX ? -1 : ans;
    }
};