C++

Forum

 
How to decrease time complexity

Pen72 (74)
Given sequence A=(a1,a2...an)
find Kth Smallest Element in iteration A[1,k],A[a,k+1]...A[1,n]

For the Input Format, the first line is n and k,
the second line is sequence A

Sample Input 0

5 2
9 8 1 2 0

Sample Output 0

9 8 2 1

Explanation:
A[1,2]=(9,8), the 2nd smallest element is 9
A[1,3]=(9,8,1), the 2nd smallest element is 8
A[1,4]=(9,8,1,2), the 2nd smallest element is 2
A[1,5]=(9,8,1,2,0), the 2nd smallest element is 1

Below is my attempt, can pass test case 0 but appears to be time out after test case 1, how can I lower time complexity

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
using namespace std;



int main() {
int n,k,l,q=0;
cin >> n >> k;
vector<int>arr(n);
vector<int> arr2(n);

for(int j=0;j<n;j++)
cin >> arr[j];

vector<int>::iterator it;
for(int i=0;i<n-k+1;i++)
{
arr2=arr;
for(l=0;l<k-1;l++)
{
it = min_element(arr2.begin(), arr2.begin()+k+q);
*it=INT_MAX;

}
cout<<*(min_element(arr2.begin(),arr2.begin()+k+q))<<" ";

q++;
}


return 0;

}
Last edited on
salem c (3700)
Double posted here as well
https://www.cplusplus.com/forum/beginner/282637/

Read this -> https://www.cplusplus.com/articles/jEywvCM9/
Go and edit your other posts for readability.

Pen72 (74)
noted, edited
Last edited on
lastchance (6980)
- you don't need arr2
- you don't need to reconsider the whole advancing array each time - just the effect of adding a single element
Last edited on
Pen72 (74)
-If I didn't copy an extra array, wouldn't the array be affected since the value has been changed and the following iterations will go wrong.
-What function can I use to achieve it
lastchance (6980)
You only need to store K additional elements (in order) at any one time. A multiset would probably do that.
Last edited on
Pen72 (74)
I've modified the code using multiset the run time improved, but still time out after three test cases, what else can I do

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
#include <bits/stdc++.h> 
using namespace std;



int main() {
    
    
    multiset<int> s; 
    multiset<int>::const_iterator it;
    int n,k;
    cin >> n >> k;
    int arr[n];
    
    for(int j=0;j<n;j++)
     cin >> arr[j];


    for(int i=0;i<k;i++)
     s.insert(arr[i]);
     it=next(s.begin(),k-1);
     cout<<*it<<" ";
    
    for(int i=k;i<n;i++)
    {   
        s.insert(arr[i]);
        it=next(s.begin(),k-1);
        cout<<*it<<" ";
    }

return 0;

}
Last edited on
lastchance (6980)
As far as your algorithm is concerned, your multiset only ever needs to hold the smallest k elements. So:
- if the proposed element you add to the set would be equal to or larger than the biggest element of the set ... then you DON'T need to insert it;
- if you do add an element to the set then you can subsequently remove the biggest element; this will keep the set small and hence quick to insert in;
- the next value that you write out will be either the last one (if nothing was inserted), the new one (if it is the smallest) or the element just one place away in the set. You don't have to iterate through a large number of values with it=next(s.begin(),k-1);


From the c++ perspective, in standard c++ the following line would (currently) be illegal:
int arr[n];
as (at the moment) a c-style array size needs to be known at compile time.
Pen72 (74)
I've done the first two, but not sure how to implement the last one
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
#include <bits/stdc++.h> 
using namespace std;



int main() {

    multiset<int> s; 
    multiset<int>::const_iterator it;
    int n,k,max=INT_MIN;
    cin >> n >> k;
    vector<int> arr(n);
    
    for(int j=0;j<n;j++)
     cin >> arr[j];


    for(int i=0;i<k;i++)
    {
        if(arr[i]>=max)
         max=arr[i];
        s.insert(arr[i]);
    }
     it=next(s.begin(),k-1);
     cout<<*it<<" ";
    
    for(int i=k;i<n;i++)
    {   
        if(arr[i]>max)
         max=arr[i];
        
        if(arr[i]<=max)
        { 
            s.insert(arr[i]);
            s.erase(prev(s.end()));
            it=next(s.begin(),k-1);
         }
        
        
        cout<<*it<<" ";
    }

return 0;

}
Last edited on
lastchance (6980)
A set or multiset always sorts itself. If you make sure that you only have k elements in your multiset all the time then the kth smallest is just whichever is at the large end of the multiset.
Last edited on
Pen72 (74)
Problem solved, thank you!
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;

int main()
{
   int n, k;
   cin >> n >> k;
    
   vector<int> A(n);
   for ( auto &e : A ) cin >> e;

   multiset<int,greater<int>> S( A.begin(), A.begin() + k );
   cout << *S.begin() << ' ';

   for ( int i = k; i < A.size(); i++ )
   {
      if ( A[i] < *S.begin() )
      {
         S.insert( A[i] );
         S.erase( S.begin() );
      }
      cout << *S.begin() << ' ';
   }
}
Topic archived. No new replies allowed.