그래서 여기에 해결책이 있습니다. 읽기 쉽도록 여기에서 작업을 반복하겠습니다. 모든 작업은 동일한 명령문으로 시작합니다.

1에서 1000까지의 정수 시퀀스가 ​​있는 배열이 있습니다.

[1, 2, 3, 4, 5, ..., 1000]

1. 쉬움

값이 x인 항목이 제거되어 배열이 다음과 같이 되었습니다.

[1, 2, 4, 5, ..., 1000]

그런 다음 배열이 섞였습니다. x 시간과 O(n) 메모리에서 O(1)를 찾는 방법은 무엇입니까?

해결책

모든 항목을 합산하고 500500에서 결과를 뺍니다(1에서 1000까지의 정수 합계).

2. 더 열심히

값이 x인 항목이 x - 1로 대체되어 배열이 다음과 같이 되었습니다.

[1, 2, 2, 4, 5, ..., 1000]

그런 다음 배열이 섞였습니다. 다시, x 시간과 O(n) 메모리에서 O(1)를 찾아야 합니다.

해결책

모든 요소를 ​​요약하면 아무 것도 제공되지 않습니다. 항상 500499입니다. 값을 "증폭"하는 방법이 있으므로 3–1이 495–1과 다른 결과에 영향을 미칠까요? 예, 하나가 있으며 항목을 제곱하는 것입니다.

물론,

트리플 엑스

로 대체되었다

x−1x - 1x−1

, 이는 결과(제곱합)가 다음과 같이 예상 값보다 작아짐을 의미합니다.

d=x2−(x−1)2==x2−x2+2x−1==2x−1
d = x^2 - (x - 1)^2 =\newline
= x^2 - x^2 + 2x - 1 =\newline
= 2x - 1
d=x2−(x−1)2==x2−x2+2x−1==2x−1


찾다

ddd

, 예상 값에서 실제 제곱합을 뺍니다. 1에서 1000까지의 제곱합은 333,833,500입니다. 그 다음에,

x=d+12
x = {d + 1\over 2}
x=2d+1​

네, 간단합니다!

3. 하드

값이 x인 항목은 y로 대체되었습니다. 여기서 y는 1에서 1000 사이의 정수이므로 배열은 다음과 같습니다.

[1, 2, 9, 4, 5, ..., 1000]

배열이 뒤섞였고, 당신의 임무는 x 시간과 y 메모리에서 O(n)와 O(1)를 찾는 것입니다.

해결책

값이나 제곱을 합산하면 아무 것도 얻을 수 없지만 둘 다 수행하면 어떻게 될까요? 우리는 대체할 수 있습니다

요이

~와 함께

x−kx - kx−k

어디

크크

모든 정수이며 음수일 수 있습니다. 찾다

크크

우리는 모든 항목을 합하고 500500에서 결과를 빼서 즉시 제공합니다.

크크

. 그런 다음 두 번째 문제와 유사한 공식을 사용할 수 있습니다.

d=x2−(x−k)2==x2−x2+2kx−k2==2kx−k2==k(2x−k),
d = x^2 - (x - k)^2 =\newline
= x^2 - x^2 + 2kx - k^2 =\newline
= 2kx - k^2 =\newline
= k(2x - k),
d=x2−(x−k)2==x2−x2+2kx−k2==2kx−k2==k(2x−k),


어디

ddd

예상 제곱합과 실제 제곱합의 차이입니다.

그리고 마지막으로,

x=12(dk+k)y=x−k
x = {1\over 2}\left( {d\over k} + k\right)
\newline
y = x - k
x=21​(kd​+k)y=x−k

이 문제를 해결하는 것이 즐거웠기를 바랍니다!