Clever Geek Handbook

Smart way to calculate position in an array (C ++)

For performance in an O (n ^ 2) algorithm, I want to halve the complexity. Basically, I have the structure of this form:

0   1   2   3   4   5
----------------------
0                     | 1
1,  2                 | 2
3,  4,  5             | 3
6,  7,  8,  9         | 4
10, 11, 12, 13, 14    | 5
15, 16, 17, 18, 19, 20| 6

So I created a size vector ((1+n)*n/2)

- obviously an arithmetic sum. The point is that I now need to calculate each position forward and backward. As an example, if I want to calculate the position in the column 2

and row 5

, I can calculate it like this:

int get_position(int x, int y)
{
    int smaller = min(x, y);
    int greater = max(x, y);
    return ((1 + greater) * greater / 2) - greater + smaller;
}

Question: how can I calculate it back? In other words, for example, from position No. 17

I would like to receive 2

and 6

.

Or maybe there is a better way to do this in C ++? (some structure will simplify)

EDIT I am looking for a way to calculate this in O (1). He exists?

+3


source to share


3 answers


Yes, there is an O (1) solution.

Mathematically larger index:

i = [sqrt(2n + 1/4) + 1/2]

(square brackets " []

" denoting truncation to an integer).



It might be difficult to correctly compute this in floating point.

Smaller index:

j = n - i*(i-1) / 2
+5


source


First of all - with indexing "y" will always be greater than "x", so you can remove calls to min function. To get an (x, y) pair from the index, there will be two steps:



y = (integer solution to (index) = (y+1)*y / 2) + 1
x = index - y*(y+1)/2
+2


source


This is not the square of N, as we can eliminate all arrays going down and search the correct array using the anchor points.
We first check the first number of each array and expect it to be between arri [0] and arri + 1 [0].
After that, you can use the Binary search algorithm to find the correct number in the array.
Binary search is log n and I can't apologize for the time it took for the first part, but I'm assuming log n. So this operation can be done in log n time

0


source






More articles:


All Articles