J.
BAN USERvoid print_matrix(std::vector<std::vector<int> > matrix)
{
if(matrix.size())
{
int m = matrix.size();//number of rows
int n = matrix[0].size();//number of columns
int layers_number = std::min((m + 1) / 2, (n + 1) / 2);
for(int layer = 0; layer < layers_number; ++layer)
{
//print top of the layer
for(int i = layer; i < n - layer; ++i)
std::cout << matrix[layer][i] << " ";
//print right part of the layer
for(int i = layer + 1; i < m - layer; ++i)
std::cout << matrix[i][n - 1 - layer] << " ";
//print bottom of the layer
if(layer < m / 2)
{
for(int i = n - 2 - layer; i >= layer; --i)
std::cout << matrix[m - 1 - layer][i] << " ";
}
//print left part of the layer
if(layer < n / 2)
{
for(int i = m - 2 - layer; i > layer; --i)
std::cout << matrix[i][layer] << " ";
}
}
}
}
I'm not sure if I got this question right.
In case we don't need to delete nodes from graph we can use a classic graph representation, such as adjacency list or adjacency matrix.
If we implement adjacency list with std::vector it will take amortized constant time to add a new node or edge. Also there is no trouble to distinguish an edge n1->n2 from n2->n1.
Your solution has linear time complexity.
But it also has linear space complexity.
P.S. I don't think your code could be compiled because in case of non-constant N you need to allocate memory for your temp array dynamically. And if you allocate additional memory dynamically it will affect performance of your solution.
Nothing will change.
Both solutions (with XOR and sum of the arithmetic progression) will work.
But for sum-solution you will need to use a little bit different formula: N*(a1 + aN)/2
And for xor-solution you will need to xor with all numbers from a1 to aN (not from 0 to N).
It is possible to do it in linear time and using constant space.
If you don't want to create a new string and just need to modify the one you have you can reverse characters in the string, and then reverse characters in each word.
If it is OK to create a new string you just need to go from the end of the original string and keep index of the end of the current word. And as soon as you reach any separate character simply copy each character from input string to output string from current index to word's end index and update word's end index.
If we need to find one missing value from N successive numbers we can XOR all values that we have with each other and with numbers from 0 to N. And because:
a xor a = 0
a xor 0 = a
(a xor b) xor b = a
as a result we will have our missing number.
It has the same time complexity as the solution with finding sum but we won't get overflow.
And what if we need to return n-th max value (i.e. return the smallest one) in this case it would be definitely not O(n).
- J. June 28, 2013Selection search will work, but with square time complexity.