a very clear cpp solution with comment


  • 0
    W
    class Solution {
    public:
        struct node{
            int freq;
            int l;
            int r;
        };
        
        int findShortestSubArray(vector<int>& nums) {
            if(nums.empty()) return 0;
            //create a hash table to record the frequency, first place and last place of a unique number.
            std::unordered_map<int,node> hash;
            for(int i=0; i<nums.size(); ++i){
                if(hash.find(nums[i])!=hash.end()){
                    hash[nums[i]].freq++;
                    hash[nums[i]].r = i;
                }
                else{
                    hash[nums[i]].freq = 1;
                    hash[nums[i]].l = i;
                    hash[nums[i]].r = i;
                }
            }
            //then we find out the number with highest frequency and shortest length.
            int degree = INT_MAX , maxf = 0;
            for(auto n:hash){
                if(n.second.freq>=maxf){
                    if(n.second.freq==maxf) degree = min(degree, n.second.r-n.second.l+1);
                    else degree = n.second.r-n.second.l+1;
                    maxf = n.second.freq;
                } 
            }
            return degree;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.