题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int minimumIndex(vector<int>& nums) {
int res=-1;
int n=nums.size();
unordered_map<int,int> mp1,mp2;
multiset<pair<int,int>> st1,st2;
for(int i=0;i<n;i++) mp2[nums[i]]++;
for(auto [k,v]:mp2) st2.insert({v,k});
for(int i=0;i<n-1;i++)
{
int x=mp1[nums[i]];
if(x!=0)
{
st1.extract({x,nums[i]});
}
mp1[nums[i]]++;
st1.insert({x+1,nums[i]});
int y=mp2[nums[i]];
mp2[nums[i]]--;
st2.extract({y,nums[i]});
if(y-1!=0)
st2.insert({y-1,nums[i]});
bool flag=true;
int lastx,lasty;
if(st1.size()>=2)
{
auto it=st1.rbegin();
if((*prev(it)).first==(*it).first) flag=false;
if((*it).first*2<=i+1) flag=false;
lastx=(*it).second;
}
else if(st1.size()==1) lastx=(*st1.begin()).second;
if(st2.size()>=2)
{
auto it=st2.rbegin();
if((*prev(it)).first==(*it).first) flag=false;
if((*it).first*2<=(n-i-1)) flag=false;
lasty=(*it).second;
} else if(st2.size()==1) lasty=(*st2.begin()).second;
if(lastx!=lasty) flag=false;
if(flag) return i;
}
return -1;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla