비슷한 유형의 요소를 함께 넣으십시오

Question

나는이 인터뷰 질문을 어딘가에서 읽고 해결하려고했습니다 : 과일 스톨 (최대 8 가지 종류의 과일에서)을 감안할 때. 유사한 유형의 과일을 모으십시오. 제한 사항 : a) 과일 스톨은 전 세계 (즉, 여분의 공간 사용 금지)입니다. b) 과일을 가져 와서 해당 유형 (getType())을 알면 비용이 많이 드는 작업이지만 스와핑은 매우 저렴한 작업입니다.

주 : 과일의 최대 유형 그래서 8

, 우리는 getType로 호출 할 필요가 있습니다 내 마음에 나올 생각 될 수 있습니다 당신은 염두에두고 모든 경우를 처리하는 코드를 작성해야() 모든 과일 (배열 요소)에 대해 적용한 다음 특정 유형에 따라 적절하게 정렬합니다. 과일의 종류를 알지 못하고이 문제를 해결할 수있는 최선의 방법이 무엇인지 모른 채 여기서 어떻게 바꿀 수 있습니까?

Answer 1

이것은 인터뷰 질문이기 때문에 과일 스톨은 배열이라고 가정합니다. 배열을 여덟 개의 영역으로 나눕니다. 각 영역은 첫 번째 영역을 제외한 각 영역의 시작 부분까지 7 개의 포인터를 사용하여 주어진 유형의 열매만을 포함합니다. 정렬되지 않은 영역의 시작 부분을 가리 키기 위해 여덟 번째 포인터를 사용하십시오.

포인터를 초기화하여 배열의 시작 부분을 가리 키도록하십시오. 포인터의 정의를 얻는 것은 까다로운 작업입니다. 왜냐하면 주어진 유형의 결실이없는 경우를 처리해야하기 때문입니다. 하나의 가능한 정의는 포인터 i가 i = 1..8에 대해 i까지의 유형으로 분류 된 과일 수를 포함한다는 것입니다. 그런 다음 처음에는 모든 포인터가 0과 1로 설정됩니다. 1 1 2 2 3 4 4 | p1 = 3 p2 = 5 p3 = 6 p4 = 8 p5 = p6 = p7 = p8 = 8

정렬되지 않은 영역의 시작 부분에있는 첫 번째 과일을 반복적으로보고 유형을 찾습니다. 최종 영역에 들어가서는 안되는 경우 최종 영역의 시작 부분에서 요소와 바꿔 포인터를 최종 영역의 시작 부분으로 이동하십시오. 두 번째 마지막 영역으로 이동해서는 안되는 경우 두 번째 마지막 영역의 시작 부분에있는 요소와 교체하고 두 번째 마지막 영역의 시작 부분으로 포인터를 이동합니다 ... 새 과일이 올바른 위치에 올 때까지 계속합니다. . 이제 첫 번째 정렬되지 않은 과일로 포인터를 이동하고 반복하십시오.

이것은 각 과일을 한 번 보았습니다. getType() 호출 횟수를 줄이면 정렬 할 수 있다고 생각하지 않습니다. 당신은 스왑의 수를 신경 쓰지 않아, 이것이 최적이라고 생각합니다.

나는 c1, c2, c1, c3, c2, c1, c4, c4로 시작하는 스왑을 보여주는 행을 넣을 것입니다.나는 cs에 글쓰기를 귀찮게하지 않을 것이고 나는 | 유형이 알려지지 않은 오른쪽 영역에서부터 모든 것이 알려진 순서대로 왼쪽에있는 영역을 나눕니다.

| 1 2 1 3 2 1 4 4

1 | 2 1 3 2 1 4 4

1 2 | 1 3 2 1 4 4

1 1 | 2 3 2 1 4 4

1 1 | 3 2 1 4 4

1 1 2 3 | 2 1 4 4

1 1 2 2 | 3 1 4 4

1 1 2 2 3 | 1 4 4

1 1 2 2 1 | 3 4 4

1 1 2 2 | 3 4 4

1 1 2 2 3 | 4 4

1 1 2 2 3 4 | 4

1 1 2 2 3 4 4 |

Answer 2

이 작업은 대개 적절한 병합 정렬로 수행 할 수 있습니다. 당신이 말한대로 즉시 각 과일의 유형을 확인하십시오. 이 여분의 메모리 (장소에서 병합 정렬을 수행하는 방법에 대한 많은 가이드)를 사용하지 않는 경우 getType()을 한 번만 호출하고 메모리 사용량이 n 인 nlog(n) 런타임이 발생합니다.

우리가 방망이에 대해 알고있는 정보가 있습니까? 질문이 보통 getType() 번의 호출을 n 번 수행하지 않아도되는 것을 피할 수있는 대체 방법을 제공하는 방식으로 말한 것 같습니다. 이것은 면접 시험관이 그것에 들어가기 시작할 때이 운동의 목표가 진화되어야한다고 생각하면 놀랄 일이 아닙니다. 이것은 구체적으로 getType()을 비싼 것으로 언급하는 이유를 설명합니다.