Challenging problem - found an idea but don't know how to code
I am now trying to address the following nice problem:
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty zero-indexed array A consisting of N integers is given.
A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value
in the array lies strictly between values A[P] and A[Q].
For example, in array A such that:
A[0] = 0 A[1] = 3 A[2] = 3
A[3] = 7 A[4] = 5 A[5] = 3
A[6] = 11 A[7] = 1
the following pairs of indices have adjacent values:
(0, 7), (1, 2), (1, 4),
(1, 5), (1, 7), (2, 4),
(2, 5), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7).
For example, indices 4 and 5 have adjacent values because there is no value in array A that lies
strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4,
and it is not present in the array.
Write a function that returns the maximum distance between indices that have adjacent values
Here is my idea: construct a map <int, int> which collects the values of the array
At this point, I would like to "sort the map", in the sense that the map now is sorted by values, and in doing so it "remembers" the key from which the newly ordered value of the array come from. After this, I check the largest adjacent pair in the sorted map, and the distance is exactly the difference between the corresponding indexes.
In the example of the array (1,4,7,3,3,5) I would obtain the "sorted map" (1,3,3,4,5,7) where the corresponding key values are now (0,3,4,1,5,2) so that I immediately can see that the max distance is given by 3-0=0.
However, I don't know how to implement this! Can anyone give a help please? Thanks in advance!
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty zero-indexed array A consisting of N integers is given.
A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value
in the array lies strictly between values A[P] and A[Q].
For example, in array A such that:
A[0] = 0 A[1] = 3 A[2] = 3
A[3] = 7 A[4] = 5 A[5] = 3
A[6] = 11 A[7] = 1
the following pairs of indices have adjacent values:
(0, 7), (1, 2), (1, 4),
(1, 5), (1, 7), (2, 4),
(2, 5), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7).
For example, indices 4 and 5 have adjacent values because there is no value in array A that lies
strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4,
and it is not present in the array.
Write a function that returns the maximum distance between indices that have adjacent values
Here is my idea: construct a map <int, int> which collects the values of the array
|
|
At this point, I would like to "sort the map", in the sense that the map now is sorted by values, and in doing so it "remembers" the key from which the newly ordered value of the array come from. After this, I check the largest adjacent pair in the sorted map, and the distance is exactly the difference between the corresponding indexes.
In the example of the array (1,4,7,3,3,5) I would obtain the "sorted map" (1,3,3,4,5,7) where the corresponding key values are now (0,3,4,1,5,2) so that I immediately can see that the max distance is given by 3-0=0.
However, I don't know how to implement this! Can anyone give a help please? Thanks in advance!
Instead of mapping index to value, you can map value to index. Then the map template will sort it for you. So in your listing you'd replace line 6 with
There's a problem though. This doesn't handle the case where multiple indexes have the same value, such as A[2] and A[5] in the example where they both equal 3. So you need a multimap instead of a map.
m[A[k]] = k;There's a problem though. This doesn't handle the case where multiple indexes have the same value, such as A[2] and A[5] in the example where they both equal 3. So you need a multimap instead of a map.
Do you know a solution to this problem? I have tried the multimap approach but I didn't really get it much out of it. If you can post a code, or link to a solution I would be most grateful.
> the corresponding key values are now (0,3,4,1,5,2) so that I immediately can
> see that the max distance is given by 3-0=0.
¿3-0=0?
¿wouldn't the bigger index distance be between 5 and 1?
> see that the max distance is given by 3-0=0.
¿3-0=0?
¿wouldn't the bigger index distance be between 5 and 1?
Topic archived. No new replies allowed.