NC562 题解 | #牛牛的魔法卡#

题意分析

• 在一个一维坐标轴上面给出若干个位置，每个位置有一个数字，两个位置的距离就是这两个位置的差值。可以从任意一点出发，问恰好经过k个不同的数值的最短的距离是多少？

思路分析

• 我们先分析思路，我们发现，为了使经过的距离尽可能短，我们应该选择的是一段区间，这段区间内不同的数值的个数为k个。走的距离就是区间的长度。所以我们需要先对题目的输入数据按照坐标的大小进行排序。方便我们进行后续的初始。
• 特判-1的情况就是所有的数值中不同的数值的个数小于k。

解法一 暴力求解

• 我们暴力枚举每个起点，然后从这个起点开始往右边移动，直到区间范围内的不同的数值的个数为k个，确定区间的右端点。维护合法区间的最小值。

• 代码如下

  • 枚举区间的左端点的时间复杂度为$O(n)O(n)$,从左端点开始进行遍历的时间复杂度为$O(n)O(n)$,所以总的时间复杂度为$O(n^2)O(n^2)$，时间复杂度过大，这种解法超时。
  • 过程中利用了set集合来存储遍历得到的数值的种类数，空间复杂度为$O(n)O(n)$

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param k int整型 
     * @param card int整型vector<vector<>> 
     * @return int整型
     */
    typedef long long ll;
    struct node{
        int num; // 表示数值
        int pos; // 表示坐标
        // 重载结构体的运算符
        bool operator < (const node &a){
            return pos < a.pos;
        }
    }Node[1000010];
    int solve(int n, int k, vector<vector<int> >& card) {
        // write code here
        int l=0,r=0,mid;
        // 先将输入转化为结构体存储
        set<int> st;
        for(int i=0;i<n;i++){
            Node[i].num=card[i][0];
            Node[i].pos=card[i][1];
            st.insert(card[i][0]);
        }
        // 特判无法找到k个不同的数值的情况
        if(st.size()<k){
            return -1;
        }
        // 按照坐标从小到大开始进行排序
        sort(Node,Node+n);
        
        
        int ans=Node[n-1].pos-Node[0].pos;
        // 枚举左端点
        for(int i=0;i<n;i++){
            st.clear();  // 利用一个set集合去重这个区间里面的数值
            for(int j=i;j<n;j++){
                st.insert(Node[j].num);
                // 如果区间内的不同的数值的个数为k个，那么这个时一个合法的区间，维护区间长度最小值
                if(st.size()==k){
                    ans=min(ans,Node[j].pos-Node[i].pos);
                    break;
                }
            }
        }
        return ans;
    }
};

解法二 双指针

• 枚举左端点，寻找最小的区间使得区间内的不同的数值的个数为k个，这不就是一个双指针的模板题吗？我们利用双指针进行求解。在枚举左指针的时候，我们让右指针一直向右边移动，直到区间内右k个不同的数值或者是右指针到达了右边界了。对于每个一个合法的区间，我们维护一个区间长度最小值即可。

• 如下图

• 代码如下
  • 首先，在过程中我们枚举了左指针，然后右指针一直向右边移动，左指针和右指针都只是遍历这个数组一遍，所以总的时间复杂度为$O(n)O(n)$
  • 在维护区间的过程中，我们利用了一个unordered_map进行哈希存储区间内某一个数值出现的次数。同时将输入的数据转化为结构体进行存储，所以总的空间复杂度为$O(n)O(n)$

class Solution {
public:
   /**
    * 
    * @param n int整型 
    * @param k int整型 
    * @param card int整型vector<vector<>> 
    * @return int整型
    */
   typedef long long ll;
   struct node{
       int num; // 表示数值
       int pos; // 表示坐标
       // 重载结构体的运算符
       bool operator < (const node &a){
           return pos < a.pos;
       }
   }Node[1000010];
   unordered_map<int, int> mp; // 用来记录某一个数值出现的次数
   int solve(int n, int k, vector<vector<int> >& card) {
       // write code here
       int l=0,r=0,mid;
       // 先将输入转化为结构体存储
       set<int> st;
       for(int i=0;i<n;i++){
           Node[i].num=card[i][0];
           Node[i].pos=card[i][1];
           st.insert(card[i][0]);
       }
       // 特判无法找到k个不同的数值的情况
       if(st.size()<k){
           return -1;
       }
       // 按照坐标从小到大开始进行排序
       sort(Node,Node+n);
       
       
       int ans=Node[n-1].pos-Node[0].pos;
       
       int cnt=0; //用来标记这个区间内有多少个不同的数值
       for(int i=0,j=0;i<n;i++){
           // 需要满足j在i的右边，同时j没有越界，同时此时这个区间内的不同的数值还不足k个
           while(i<=j&&j<n&&cnt<k){
               mp[Node[j].num]++;
               if(mp[Node[j].num]==1){
                   cnt++;
               }
               j++;
           }
           // 如果这个区间内满足k个不同的数值，那么维护区间长度最小
           if(cnt==k){
               ans=min(ans,Node[j-1].pos-Node[i].pos);
           }
           // 更新左边界的数值
           mp[Node[i].num]--;
           if(mp[Node[i].num]==0) cnt--;
       }
       
       
       return ans;
   }
};