360笔试k卷编程第二题
发布于 2017-08-26 21:40 2345 次浏览 0 赞 来自 笔试面试  

//只能通过80%,不知什么问题,难道是双重循环导致复杂度太大???

#include<iostream>

#include<vector>

using namespace std;

int main()

{

       int n;

     while(cin>>n)

     {      

      vector<int> num(n);

      for(int i=0;i<n;i++)

           cin>>num[i];

      vector<int>res(n,0);

      for(int i=1;i<n;i++)

          {

               for(int j=0;j<i;j++)

                   if(num[i]<num[j])

                         res[i]++;

           }

       for(int i=0;i<n-1;i++)

            cout<<res[i]<<" ";

       cout<<res[n-1]<<endl;

       res.clear();

       num.clear();

     }

}


2 条回复

20w的数据啊。你O(n^2)的复杂度怎么可能过....

2017-08-26 21:41

http://www.lintcode.com/en/problem/count-of-smaller-number-before-itself/看这道题吧,线段树

2017-08-26 21:44
2
添加回复
回到顶部