https://leetcode.com/contest/leetcode-weekly-contest-54/problems/degree-of-an-array/

[Idea]

[實作邏輯]


Use a map to store following info:
{number, {freq, {start, end}}}

Then reuse start to store (end - start +1).

Finally, apply multi-key sort; the 1st key is freq in ascending order & then distance(2nd key) in descending order.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>


using namespace std;

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        map< int, pair<int/*count*/, pair<int/*first*/, int/*last*/> > > statistic;
        for (int i = 0; i < nums.size(); i++) {
            if (statistic.find(nums[i]) != statistic.end()) {
                statistic[nums[i]].second.second = i;
                statistic[nums[i]].first++;
            } else {
                statistic.insert(make_pair(nums[i], make_pair(1, make_pair(i, i))));
            }
        }

        map< int, pair<int/*count*/, pair<int/*first*/, int/*last*/> > >::iterator it;
        for (it = statistic.begin(); it != statistic.end(); it++) {
            it->second.second.first = it->second.second.second - it->second.second.first + 1;
        }

        map< int, pair<int/*count*/, pair<int/*first*/, int/*last*/> > >::iterator res;
        int maxFreq = 0;
        for (it = statistic.begin(); it != statistic.end(); it++) {
            if (it->second.first > maxFreq) {
                res = it;
                maxFreq = it->second.first;
            } else if (it->second.first == maxFreq) {
                if (it->second.second.first < res->second.second.first) {
                    res = it;
                }
            }
        }
        printf("id = %d freq = %d first = %d second = %d\n", res->first, res->second.first, res->second.second.first, res->second.second.second);
        return res->second.second.first;
    }
};

int main() 
{
    int x[5] = {1, 2, 2, 3, 1};
    std::vector<int> v(x, x + sizeof x / sizeof x[0]);
    Solution sol;
    sol.findShortestSubArray(v);
    system("pause");
}