C++에서 정렬된 배열의 k번째 누락된 요소

이 튜토리얼에서는 주어진 정렬된 배열에서 k번째 누락된 요소를 찾는 프로그램을 작성할 것입니다.

주어진 정렬되지 않은 배열에서 최소값에서 최대값까지 누락된 k 번째 숫자를 찾습니다. 문제를 해결하는 단계를 살펴보겠습니다.

• 정렬된 배열을 초기화합니다.
• 두 변수 차이를 초기화하고 k를 사용하여 계산합니다.
• 배열을 반복합니다.
  • 현재 요소가 다음 요소와 같지 않은 경우.
    • 두 숫자의 차이를 찾으세요.
    • 차이가 k보다 크거나 같으면 현재 요소에 개수를 더한 값을 반환합니다.
    • 그렇지 않으면 개수에서 차이를 뺍니다.
• 반환 -1.

예

코드를 봅시다.

#include <bits/stdc++.h>
using namespace std;
int findMissingNumber(int arr[], int k, int n) {
   int difference, count = k;
   for(int i = 0 ; i < n - 1; i++) {
      if ((arr[i] + 1) != arr[i + 1]) {
         difference = arr[i + 1] - arr[i] - 1;
         if (difference >= count) {
            return arr[i] + count;
         }else {
            count -= difference;
         }
      }
   }
   return -1;
}
int main() {
   int arr[] = { 1, 2, 3, 5, 10 }, n = 5;
   int k = 3;
   cout << findMissingNumber(arr, k, n) << endl;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

7

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.