정렬 및 회전 목록에 요소 삽입

Question

정렬되고 회전 된 요소 목록이 제공됩니다. 요소는 오름차순 또는 내림차순 순으로 정렬됩니다. 예를 들어, 다음과 같이 정렬 된 요소의 목록이 있습니다.

10,12,14,16,18,20,51,53,54,59 

이제이 목록은 X 번만큼 순환되어 다음과 같이 보입니다.

51,53,54,59,10,12,14,16,18,20 

이 목록에 요소를 삽입하려면 가장 효율적인 방법이 무엇입니까? 내가 코드를 기대하고 있지 않다

59 사이 (10) 알고리즘의 논의는 내가 '무엇을 오히려 목록이 선형 방식으로 횡단하는 경우 삽입 할 요소에 대해

는, 13, 잘못된 삽입이 발생할 수 있습니다 앞으로 기대하고 있습니다. 값 21은 처음/마지막 요소로 삽입 될 수 있습니다. - 삽입 된 요소가 될 것과 같은 경계 조건을 고려하십시오. 첫 번째 요소와 마지막 요소는 같은 값입니다.

Answer 1

이것은 log (N) 시간으로 해결할 수 있습니다. 짧게 :

1. 목록의 가장 큰/가장 작은 요소를 찾으려면 이진 검색을 사용하십시오. 이것은 O (logN)를 취합니다. 구현은 당신이보고있는 요소를 목록의 첫 번째 요소와 비교하는 것만으로 쉽습니다.
2. 바이너리 검색을 사용하여 목록의 필요한 부분 만 사용하여 새 요소를 삽입하십시오. 이것은 O (logN)도 취합니다.

포인트 1에 대한 추가 정보 : 51,53,54,59,101214161820에서 가장 큰 요소를 찾아야한다고 가정 해보십시오.

먼저 중간 요소를 선택합니다 (예 : 12). 12는 51보다 작으므로 가장 큰 요소는 12에서 왼쪽입니다. 간격을 반으로 나누면 54가됩니다. 54가 51보다 크므로 가장 큰 요소는 54와 12 사이입니다.

Answer 2

X '회전'동안 최소 요소를 추적합니다. 그런 다음 해당 절반에서 이진 검색을 사용하십시오.

Answer 3

목록에서 효율적으로 임의 액세스가 가능하다고 가정하면 오프셋이있는 이진 검색입니다. 올바른 색인을 찾은 경우 요소 1 색인 위치를 왼쪽으로 이동합니다. 이것은 검색에 대한 복잡성 O (log n) 및리스트 복사 연산에 대한 O (n)을 갖는다.

Answer 4

하나의 새로운 요소 인 경우 같은

• 같은 경계 조건에 대한 내가 생각 해낸 해결책,

  1.Check/첫 번째와 마지막 요소 W 또는 그 반대의 경우도 마찬가지

• 하는 경우 나 새로운 요소 첫 번째 또는 마지막 요소와 동일합니다.

위 조건 중 하나라도 충족되면 첫 번째 위치에 요소를 삽입합니다. 중간 요소 2.Take

• 체크하면 새로운 요소 == 중동 요소 -이 위치에 새로운 요소를 삽입
• 확인 새로운 요소입니다/중동 요소 w과 오른쪽 가장 또는 B 그것은 가장 왼쪽과 가장 오른쪽 요소입니다.

3. 부품 수 b/w 왼쪽 - 중간 또는 중간 - 오른쪽 위 조건을 기반으로합니다. 요소 번호 < = 2 인 경우

• , 새로운 요소를 삽입 좌측 중간 OR 오른쪽 중간
• 않으면 새로운 좌측, 중앙 및 우측 요소를 계산하고 수행 승 단계/2

B

Answer 5

물론 실제 질문은 필요한 데이터 구조와 효율성에 관한 것입니다.

: 순서 (내림차순 오름차순 /)

그렇지 않으면 4,2 해석 중 하나로 될 수있다, 당신은 순서에 대해 알아야 할 "최소"

참고있다가 무엇

• • 2,4 1 회 오름차순 및 1 회 회전
  • 4,2 하강

  3 개 요소에서 최대 값과 최소값이 함께 설정되는 방식 때문에 4,2,3이 오름차순이고 한 번 회전 한 것으로 추측 할 수 있습니다.

  실제로 회전을 쉽게하는 원형 구조를 사용해야합니다. 그런 다음이 구조에 접근 유지할 수 있습니다 :

  • 최소 감안할 때 현재 시작

  을 가리키는 최소

• 를 가리키는, 그것의 오른쪽에 쉽게 (하나 개의 비교입니다 이웃)가 주문이 무엇인지 알 수 있습니다. 그리고 그 시점부터 Circular 구조에 삽입하는 것도 쉽습니다.