C++ solution, any possible way to optimize this code please?


  • 0
    // idea: 1. store numbers with their number of repeated into a map.
    //       2. sort the map in descending order based on their number of repeated 
    //          or the length between the first found index and the last found index
    //       3. after sorting the map, the first pair of the map contains the number we want, find its length between 
    //          its first found index and its last found index and return the value
    
    class Solution {
    public:
        int findShortestSubArray(vector<int>& nums) 
        {
           // key = number, value = number of repeated
            unordered_map<int, int> map;
    
            // store each number into map
            for (int number : nums)
            {
                // update the number of repeated
                map[number]++;
            }
    
            vector<pair<int, int>> mapVector(map.begin(), map.end());
    
            // sort map based on the number of repeated in descending order
            sort(mapVector.begin(), mapVector.end(), [&](pair<int, int>& a, pair<int, int>& b)
            {
                int len1 = getLength(a.first, nums);
                int len2 = getLength(b.first, nums);
                return (a.second > b.second) || (a.second == b.second &&  len1 < len2);
            });
    
            int length = 0;
            for (auto& pair : mapVector)
            {
                // the first pair at this point is the number with maximum frequency
                length = getLength(pair.first, nums);
                break;
            }
    
            return length;
        }
    
        
        int getLength(int number, vector<int>& nums)
        {
            int maxIndex = 0;
            int minIndex = 0;
    
            for (int i = 0; i < nums.size(); i++)
            {
                if (nums[i] == number && i >= minIndex)
                {
                    minIndex = i;
                    break;
                }
            }
    
            for (int i = nums.size() - 1; i >= 0; i--)
            {
                if (nums[i] == number && i >= maxIndex)
                {
                    maxIndex = i;
                    break;
                }
            }
    
            return maxIndex - minIndex + 1;
        }
    };
    
    

Log in to reply
 

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