leetcode 697.数组的度

题目: 传送门

一看题很水就想直接暴力。哎~ 我错了。

开始想着排序。找到最大的度对应的值，然后双指针从两边开始搜。找到相应的值左右两边相减就能得到答案了。
太天真了。其实最大度对应的值可能不止一对。当发现问题后，其实多遍历几次，多判断几次，但是为这题写长代码值得吗？ 直接用上高效的map吧。不过我不是很喜欢使用STL来解决问题。一般能降低空间复杂度，就尽量降低。
时间复杂度O(n) 解法。
使用map记录值。第一个 key就 int类型吧 ,我们也要记录数据第一次出现时对应的下标。以及数据出现的次数。
那么map中的 value我使用 pair<int, int> 来记录。第一个位置记录出现的次数。第二个记录数据第一次出现时的下标。
边遍历边更新
1，如果当前记录的最大度，比当前枚举的数据的度小，那么就跟新最大度的值。以及最大度的距离。
1. 如果当前记录的最大度，和当前枚举的数据的度一样，那么我就只更新距离。获取最小的。
1. 如果当前记录的最大度，比当前枚举的数据的度要大。那么就不处理。

话不多说，上代码

#define x first
#define y second
typedef pair<int, int> PII; // 第一个是数据出现的次数， 第二是数据第一次出现的 坐标。
using namespace std;
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, PII> map;
        int ma = 0;
        int ans = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            if (!map[nums[i]].x){
                map[nums[i]].x ++ ;
                map[nums[i]].y = i;     //记录第一次出现时的坐标。
            }
            else  map[nums[i]].x ++ ;
            if (ma < map[nums[i]].x){ // 如果遇见度更大的，则更新成最小的。
                ma = map[nums[i]].x;
                ans = i - map[nums[i]].y + 1;
            }
            if (ma == map[nums[i]].x) // 如果遇见度相同的 则更新成最小的。
            {
                ans = min(ans, i - map[nums[i]].y + 1);
            }
        }
        return ans;
    }
};

喜欢的话，给博主赏一杯冰阔乐吧