C++で配列内のK番目の奇数を見つける方法

このチュートリアルでは、与えられた配列の中からK番目の奇数を見つけるプログラムをC++で作成します。配列の走査と条件分岐の基本的な考え方を学べる、初心者向けの良い例題です。

問題を解く手順

以下の手順に従って問題を解いていきましょう。

• 配列と値kを初期化します。
• 配列を先頭から順に走査します。
  • 現在の要素が奇数であれば、kの値を1減らします。
  • kが0になった時点で、その要素を結果として返します。
• 配列全体を走査してもK番目の奇数が見つからない場合は、-1を返します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int findKthOddNumber(int arr[], int n, int k) {
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 1) {
            k--;
        }
        if (k == 0) {
            return arr[i];
        }
    }
    return -1;
}

int main() {
    int arr[] = { 4, 5, 22, 1, 55 };
    int k = 3;
    cout << findKthOddNumber(arr, 5, k) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

55

コードの解説

この例では、配列 {4, 5, 22, 1, 55} の中から3番目の奇数を探しています。処理の流れは以下の通りです。

• 最初の要素「4」は偶数なのでスキップされます。
• 2番目の要素「5」は1番目の奇数なので、kは3から2になります。
• 3番目の要素「22」は偶数なのでスキップされます。
• 4番目の要素「1」は2番目の奇数なので、kは2から1になります。
• 5番目の要素「55」は3番目の奇数なので、kが0になり、55が返されます。

なお、元のコードではループ条件が i <= n となっており、配列の範囲外にアクセスする可能性があるため、i < n に修正しています。これは未定義動作を防ぐために重要なポイントです。

まとめ

このように、配列を一度走査するだけでK番目の奇数を見つけることができます。計算量はO(n)となり、非常に効率的なアルゴリズムです。同様の手法は、K番目の偶数や特定の条件を満たす要素の検索にも応用できます。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。