C++のソートされた配列でk番目に欠落している要素

このチュートリアルでは、指定された並べ替えられた配列でk番目に欠落している要素を見つけるプログラムを作成します。

指定されたソートされていない配列で最小から最大まで欠落しているk番目の数値を見つけます。問題を解決するための手順を見てみましょう。

• ソートされた配列を初期化します。
• 2つの変数の差を初期化し、kでカウントします。
• アレイを反復処理します。
  • 現在の要素が次の要素と等しくない場合。
    • 2つの数値の違いを見つけます。
    • 差が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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。