3 ms·
One naive solution is to realize that you can move (remove/reinsert) any element with two reversals. For example, given: [1 2 3 4 5 6] You can reverse elemen
by endtime 18y ago
One naive solution is to realize that you can move (remove/reinsert) any element with two reversals. For example, given:
[1 2 3 4 5 6]
You can reverse elements 1-5 (if indexing starts at 0):
[1 6 5 4 3 2]
And then reverse elements 1-4:
[1 3 4 5 6 2]
This moves the element in position 1 to position 5. Generally, to move the element in position x to position y (shifting everything else to make room for it), do the following:
def move(v, x, y):
v.reverse(x, y)
if y > x:
v.reverse(x, y-1)
else
v.reverse(x+1, y)
return v
Given this ability to move/insert elements, you can implement several sort algorithms. In fact, it's easy to see that there's a O(n * x) sort here, where x is the runtime of the reversal operator.
- spaghetti 18y ago"You can reverse N contiguous items in V at a time." When you reverse elements 1-5 you're assuming N == 5. When you reverse elements 1-4 you're assuming N == 4. I think this violates the problem statement that N is fixed.
- Timothee 18y agoI don't think it works that way. You're also given an integer N which is greater than or equal to 2 and less than V.size(). You can reverse N contiguous items in V at a time. So, you always revert the same number of elements in the vector. In your example, you revert 5 elements and then 4. Your example would give the following sequence: [1 2 3 4 5 6] [1 6 5 4 3 2] [3 4 5 6 1 2] [3 2 1 6 5 4] [5 6 1 2 3 4] [5 4 3 2 1 6] [1 2 3 4 5 6] For that case (6 elements and N=5), it looks like not many vectors V have a solution... but I'm too tired to keep going :)
- endtime 18y agoWhoops, you're right, I didn't read it correctly.