첫 번째 요소가 가장 크고 두 번째 요소가 가장 작은 식으로 배열을 정렬합니다. 여분의 공간

Question

없이 할 질문은 다음과 같습니다

는 첫 번째 요소가 가장 큰 것으로 일종의 그것을 같은 방식으로, 정렬되지 않은 배열을 감안할 때, 두 번째 요소는 가장 작은, 세 번째 요소는 두 번째로 큰,

추가 작업 : 추가 공간을 사용하지 않고도 작업을 수행 할 수 있습니까?

예 :

[2, 4, 3, 5, 1] ​​-> [5, 1, 4, 2, 3] I는없는 배열을 정렬 할 수 있도록하려는

여분의 공간을 사용합니다. 가장 효율적인 솔루션은 무엇입니까? 나는 배열을 통해 반복되는 O (n) 솔루션 만 생각해 볼 수 있습니다. 그 다음 큰 요소와 그 다음으로 작은 요소를 찾습니다. 보다 효율적인 솔루션이 있습니까?

관련 질문 Sorting an array with alternate smallest and largest values 및 Sorting an array with alternate smallest-largest values을 살펴 보았지만 답변이 제 질문에 도움이되지 않았습니다.

Answer 1

전제 조건 : deque.

1. 배열을 배열한다.

루프)

2.pop_back (배열) - 전 2 위치에서 *> 그 요소를 삽입한다.

예) 1, 2, 3, 4, 5, 6,

a) 7 7 (0 삽입) -> 1 2 3 4 5 6 => 7 1 2 3 4 5 6

b) 6 (삽입 2) -> 7 1 2 3 4 5 => 7 1 6 2 3 4 5

c) 5 (삽입 4) -> 7 1 6 2 3 4 => 7 (완료) 1 6 2 5 3 4

복잡 어쩌면 O (nlog (N)) + O (N/2)