배열에서 누락 된 정수를 찾는 가장 효율적인 방법

정수 1 - 100 (임의로 삽입 됨)의 배열이 주어지면 하나의 정수가 배열에서 제거됩니다. 누락 된 정수를 찾는 가장 효율적인 방법은 무엇입니까?배열에서 누락 된 정수를 찾는 가장 효율적인 방법

2014-01-12 KingKongFrog

가능한 중복입니다 (http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-array-of-numbers) – baci

2.8k 담당자는 사용자가 알기를 기대합니다. 질문에서 한 연구의 비트의 증거를 보여 ... – Dukeling

당신이 정수를 아시는 바와 같이, 그들 모두의 합합니다

(1+N)*N/2 = (1+100)*100/2 = 5050

을 이제 배열에있는 것들의 합을 빼지 (S '). 그 차이는 찾지 못한 번호입니다 (그래서).

시간 복잡도는 O (N)이며 더 빨리 해결할 수는 없습니다. 확실히 배열을 한 번 읽을 필요가 있기 때문입니다. [숫자의 배열 번호를 누락을 발견하는 가장 빠른 방법]

은

출처

2014-01-12 21:46:06

이것은 N이 매우 큰 것을 고려해 볼 때 최적의 대답이 아니므로 오버플로를 가질 수 있습니다. –

우리가 여기에 1..100 범위를 말하고 있기 때문에 최적입니다. 우리가 더 큰 수녀를 얻은 경우에, 우리는 여전히 이것을 사용할 수 있지만 배열을 기반으로 한 큰 정수에는 우리 자신의 정수 클래스를 구현합니다. –

MZetko 이미 기본적인 경우에 대답하지만, 여기에 4 개 배열을 정렬 할 수 있습니다이 다른 솔루션 또는 분류되지 않은

https://github.com/KartikTalwar/Algorithms/blob/master/Arrays/Find%20only%201%20missing%20number%20from%20an%20array/Find1MissingElementFromArray.py

출처

2014-01-12 21:48:46 Kartik

그냥 링크를 제공하는 것보다는 여기에 답의 핵심 부분을 포함시키는 것이 바람직합니다 (http://meta.stackexchange.com/a/8259). 추가 참조 링크를 제공하십시오. 만약 당신이이 일을 끝내지 않았다면, 답을 게시하는 대신 질문에 간단히 [의견 남기기] (http://stackoverflow.com/privileges/comment)를 고려해야합니다. – Dukeling

다음 번에 그 점을 염두에 두겠다. 그러나 변명 할 때, 나는 링크에 답을 썼다. – Kartik

게시물은 장거리 노선을 위해 여기에있다. 새로운 게시물을 지침에 따라 작성하고 기존 게시물을 편집하지 말라. (즉,이 게시물). – Dukeling

배열에서 누락 된 정수를 찾는 가장 효율적인 방법

답변

관련 문제