[아카이브] 순수수학, 물리학, 화학 등 : 거래와 무관한 두뇌 트레이닝 퍼즐 - 페이지 584

[MikeM]

alsu :

한 번에:

같은 크기의 배열의 빈 복사본을 만들고 2로 초기화합니다.

배열의 시작 부분부터 시작합니다. 우리는 1을 만났습니다 - 우리는 처음부터 사본에 쓰고 3을 만났습니다 - 우리는 끝에서 시작하여 사본에 씁니다.

그리고 듀스를 사용한 초기화(평균 66% 쓸모 없음)는 통과가 아닌가요?
또한 세 개의 포인터를 동시에 추적해야 합니다!

[Dmitry Fedoseev]

GaryKa :

문제를 드리겠습니다.

보얀은 물론이지만 인터뷰에서 지식의 신조로 배열을 정렬))

그래서 정렬 문제

1, 2 및 3이 임의의 순서로 배치된 N 셀의 배열이 있습니다.

가장 최적의 정렬 알고리즘을 구축합니다.

한 번의 패스로 계산하고 두 번째 패스 에서 배열을 채웁니다 .

[Alexey Subbotin]

alsu :

한 번에:

같은 크기의 배열의 빈 복사본을 만들고 2로 초기화합니다.

배열의 시작 부분부터 시작합니다. 우리는 1을 만났습니다 - 우리는 처음부터 사본에 쓰고 3을 만났습니다 - 우리는 끝에서 시작하여 사본에 씁니다.

사본이 없는 경우(그렇지 않으면 사본을 작성하는 것이 별도의 패스라고 합니다)

n=0, m=0

배열의 시작 부분부터 시작합니다. 우리는 1을 만났습니다 - 배열의 시작 부분에서 n 번째 요소로 변경합니다. 1과 같지 않습니다(구성상 항상 2가 됨), n++, 3을 만났을 경우 - m 번째 요소로 변경 끝에서, 3과 같지 않음, m++, 그리고 교체하려면 1이 있으면 첫 번째 부분에 표시된 작업을 수행합니다.

[Alexey Subbotin]

alsu :

사본이 없는 경우(그렇지 않으면 사본을 작성하는 것이 별도의 패스라고 합니다)

n=0, m=0

배열의 시작 부분부터 시작합니다. 우리는 1을 만났습니다 - 우리는 배열의 시작 부분에서 n 번째 요소로 변경합니다. 1이 아닌 1 (구성상 항상 2가 됨), n ++, 3을 만났을 때 - 끝에서 m 번째로 변경합니다. 3, m++와 같으며 1을 대체하려면 첫 번째 부분에 표시된 작업을 수행합니다.

평균적으로 절반의 패스와 교환을 위한 동일한 시간

[sand]

alsu :

사본이 없는 경우(그렇지 않으면 사본을 작성하는 것이 별도의 패스라고 합니다)

n=0, m=0

배열의 시작 부분부터 시작합니다. 우리는 1을 만났습니다 - 배열의 시작 부분에서 n 번째 요소로 변경합니다. 1과 같지 않습니다(구성상 항상 2가 됨), n++, 3을 만났을 경우 - m 번째 요소로 변경 끝에서, 3과 같지 않음, m++, 그리고 교체하려면 1이 있으면 첫 번째 부분에 표시된 작업을 수행합니다.

좋은 방법.

[TheXpert]

alsu :

패스 수를 줄인다고 해서 항상 속도가 빨라지는 것은 아닙니다.

[MikeM]

두 개의 배열 요소 를 바꾸는 것은 3번의 작업입니다. 아마도 더 빠르지 않을 것입니다.

[Alexey Subbotin]

TheXpert :
패스 수를 줄인다고 해서 항상 속도가 빨라지는 것은 아닙니다.

글쎄, 최적의 기준이 설정되지 않았습니다 ...

[MikeM]

질문 하나 할게요:
A+B=...

[Dmitry Fedoseev]

alsu :

사본이 없는 경우(그렇지 않으면 사본을 작성하는 것이 별도의 패스라고 합니다)

n=0, m=0

배열의 시작 부분부터 시작합니다. 우리는 1을 만났습니다 - 배열의 시작 부분에서 n 번째 요소로 변경합니다. 1과 같지 않습니다(구성상 항상 2가 됨), n++, 3을 만났을 경우 - m 번째 요소로 변경 끝에서, 3과 같지 않음, m++, 그리고 교체하려면 1이 있으면 첫 번째 부분에 표시된 작업을 수행합니다.

좋은 생각.