C++ esay O(n) solution


  • 0
    A

    Using hashmap to record all positions of a specific value.

    class Solution {
    public:
        int findShortestSubArray(vector<int>& nums) {
            unordered_map<int, vector<int>> map;
            int degree = 0;
            int min_dis = INT_MAX;
            for(int i=0; i<nums.size(); i++) {
                map[nums[i]].push_back(i);
                int size = map[nums[i]].size();
                degree = max(degree, size);
            }
            for(auto m: map) {
                vector<int> tmp = m.second;
                if(tmp.size()==degree)
                    min_dis = min(min_dis, tmp[tmp.size()-1]-tmp[0]+1);
            }
            return min_dis;
        }
    };
    

  • 0
    S

    @AuroraWang is there a non hash-map solution?


Log in to reply
 

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