1.5.9 누락된 가장 작은 양수 찾기
문제 1-9 정렬되지 않은 배열이 주어졌을 때 배열에 없는 숫자 중 가장 작은 양수를 찾으세요.
첫 번째 해결책 범위 내 각 숫자가 배열에 있는지 무차별 대입(brute force) 방식으로 접근해 확인합니다.
해결책 1-9-1
int SmallestPositiveMissingNumber(int arr[], int size)
{
int found;
for (int i = 1; i < size + 1; i++) {
found = 0;
for (int j=0; j< size; j++) {
if (arr[j] == i) {
found = 1;
break;
}
}
if (found == 0) {
return i;
}
}
return -1;
}
분석 시간 복잡도는 O(n2)입니다.