my accepted c++ solution O(n)


  • 0
    C

    这道题目其实是确定出现频率最高的数字,然后算这个数字的起始位置和终止位置,当然有可能会出现多个数字出现次数一样,所以首先使用map进行统计,这个很容易就能想到,就想统计字符一样,然后就很简单计算这个数字的起始位置和中间位置就可以了

    class Solution {
      public:
        int findShortestSubArray(vector<int>& nums) {
           if (nums.size() == 1)
    		return 1;
    	//先用hash统计次数
    	map< int, int > hp;
    	for (int i = 0; i < nums.size(); i++)
    	{
    		if (hp.find(nums[i]) != hp.end())
    			hp[nums[i]]++;
    		else
    			hp[nums[i]] = 1;
    	}
    	multimap<int, int> m;
    	map<int, int>::iterator it;
    	for (it = hp.begin(); it != hp.end(); it++)
    		m.insert (pair<int, int>(it->second, it->first));
    
    	multimap<int, int>::iterator t = m.end();
    	t--;
    	int max = t->first;
    	vector<int> findnums;
    	while (t!=m.begin()&&t->first==max)
    	{
    		findnums.push_back(t->second);
    		t--;
    	}
    	if (m.begin()->first == max)
    		findnums.push_back(m.begin()->second);
    
    	//发现最短的数
    	int result = nums.size();
    	for (int i = 0; i < findnums.size(); i++)
    	{
    		int begin, end;
    		begin = 0;
    		end = nums.size()-1;
    		while (nums[begin] != findnums[i])
    			begin++;
    		while (nums[end] != findnums[i])
    			end--;
    		if (end - begin + 1 < result)
    			result = end - begin + 1;
    	}
    	return result; 
        }
    };
    

  • 0
    V

    map is not implemented as a hash table. Instead it's a red-black tree or other balanced BST. You should use unordered_map. Otherwise it will be O(nlogn).


  • 0
    S

    在你的最后一个for loop中,使用线性查找来找第一个和最后一个findnums[i]。
    如果原数组的数字各不相同,比如1, 2, 3, 4, 5。那么你的findnums应该就是{1, 2, 3, 4, 5}。按照你的查找方法,每找一个数字都得遍历整个数组。所以在各数字均不相同的最坏情况下,时间复杂度应该是O(n^2)吧。


Log in to reply
 

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