C 언어 배열 에서 중복 되 는 디지털 분석 및 방법
제목:n 길이 의 배열 에 있 는 모든 숫자 는 0-n-1 범위 내 에 있 습 니 다.배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 었 는 지 모 르 고 모든 숫자 가 몇 번 반복 되 었 는 지 모른다.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.예 를 들 어 길이 가 7 인 배열{2,3,1,0,2,5,3}을 입력 하면 해당 하 는 출력 은 중복 되 는 숫자 2 또는 3 입 니 다.
해법 1:배열 을 정렬 한 후에 정렬 된 배열 을 옮 겨 다 니 면 배열 에서 중복 되 는 숫자 를 알 수 있 습 니 다.
시간 복잡 도;O(nlogn);
해법 2:O(N)크기 의 해시 표를 만 들 고 배열 의 요 소 를 옮 겨 다 니 며 해시 표 에 존재 하 는 지 판단 합 니 다.해시 표 에 존재 하지 않 는 다 면 이 요 소 를 해시 표 에 넣 고 계속 스 캔 합 니 다.이 요소 가 해시 표 에 존재 한다 면 배열 에서 중복 되 는 숫자 를 찾 았 습 니 다.
시간 복잡 도:O(N),공간 복잡 도:O(N);
해법 3:주어진 배열 을 정렬 합 니 다.다음 에 i 로 표 시 된 요소:a[i]=i 라면 다음 요 소 를 검색 합 니 다.만약 에 똑 같 지 않 으 면 a[i]와 a[a]를 비교 하고 똑 같 으 면 중복 되 는 숫자 를 찾 았 습 니 다.없 으 면 숫자 를 교환 하고 순서대로 진행 합 니 다.
int DuplicateInArray(int arr[],int size)
{
int i=0;
while(i<size)
{
if(arr[i] == i)
++i;
else
{
if(arr[i] != arr[arr[i]])
{swap(arr[i],arr[arr[i]]);}
else
{return arr[i];}
}
}
return -1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 체인 시계는 뱀을 탐식하는 작은 게임을 실현한다본고의 실례는 여러분에게 C 언어 체인표가 뱀 탐식 게임을 실현하는 구체적인 코드를 공유하여 참고하도록 하였으며, 구체적인 내용은 다음과 같다. 프로젝트 이름: 뱀놀이 운영 환경: Linux 프로그래밍 언어: C 언...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
