TASK 1 • INTEGER PAIRS
I can think of an easy O(n log n + n) solution (sort), and an also easy O(2n) solution (histogram). You really aren’t going to get better than this.
seeplus and
lastchance nailed this one. (Sorry
coder777, that’s an O(n²) solution.)
TASK 2 • ROTATE RIGHT K ELEMENTS
The function signature is confused. It takes a
mutable reference to a vector and returns a
new vector? It should be either:
•
std::vector<int> rotate_right( const std::vector<int> & A, int K );
•
std::vector<int> & rotate_right( std::vector<int> & A, int K ); // or return void
The consequence is significant, because the first implies (as
lastchance stated) that the rotation is accomplished via a simple copy, while the second requires more careful thinking (assuming we wish to perform the rotate in-place). As-is it kind of implies...
both?
@
frek
All your solutions are O(NK) == O(n²).
Remember, you need to work with a solution before you jump into programming it. Pick something small you can work with (arrays of 5 and 6 elements are a good start) and see what patterns you can find as you play with them. Sometimes it just takes attacking it from different angles until things make sense.
I haven’t looked at how
std::rotate()
does things for a long, long time. But assuming an in-place rotate
and assuming I am not allowed to use
std::rotate()
, this is how I would do it:
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
|
// cl /EHsc /W4 /Ox /std:c++17 -Ddebug a.cpp
// clang++ -Wall -Wextra -pedantic-errors -O3 -std=c++17 -Ddebug a.cpp
#include <ciso646>
#include <utility>
#include <vector>
#ifndef debug
#define debug(...)
#else
#undef debug
#define debug(...) __VA_ARGS__
#endif
debug( int SWAP_COUNT = 0; )
namespace internal
{
int fix_K( int K, int N )
{
if (K < 0) return N - (-K % N);
else return K % N;
}
std::vector<int> & rotate_right( std::vector<int> & A, int K, int N )
{
using std::swap;
if ((K == 0) or (N < 2)) return A;
int a = 0;
int b = K;
while (b < N)
{
debug( SWAP_COUNT += 1; )
swap( A[a], A[b] );
a = (a + 1) % K;
b = b + 1;
}
return rotate_right( A, fix_K( K-N, K ), K ); // tailcall recursion :O)
}
}
std::vector<int> & rotate_right( std::vector<int> & A, int K )
{
// N ← A.size(); N > 0
int N = (int)A.size();
if (!N) return A;
// K ← number of elements to shift right; 0 ≤ K < N
K = internal::fix_K( K, N );
return internal::rotate_right( A, K, N );
}
#include <iostream>
#include <numeric>
int main()
{
for (int N = 0; N < 11; N++)
{
std::cout << "\nN = " << N << "\n";
for (int K = -N; K < N; K++)
{
debug( SWAP_COUNT = 0; )
std::vector<int> xs( N, 0 ); std::iota( xs.begin(), xs.end(), 0 );
std::cout << "K = " << K << ":";
for (int x : rotate_right( xs, K )) std::cout << " " << x;
debug( std::cout << " (" << SWAP_COUNT << " swaps)"; )
std::cout << "\n";
}
}
}
|
This is an O(n) in-line solution requiring O(1) extra space (for the swap).