C++で値が最も小さいK個のアイテムを検索する方法

この記事では、アイテム名とその値からなるリストと整数 k が与えられたときに、値が最も小さい K 個のアイテムを見つける方法について解説します。

問題の概要

与えられたリストの中から、値が最も小さい k 個のアイテムを取り出すことが目的です。

具体例で問題を理解しよう

入力: item-value = { {item1, 200}, {item2, 100}, {item3, 500}, {item4, 400} }、k = 2

出力: item1、item2

説明:

値が最も小さい2つの要素は、値200の item1 と値100の item2 です。

解法アプローチ

この問題は、貪欲法（グリーディ法）によって解くことができます。まず、アイテムのリストを値の昇順にソートします。ソート後のリストの先頭から k 個のアイテムを取り出せば、それが値の最も小さい k 個のアイテムとなります。

なお、同点の値が存在する場合に備えて、比較関数では値が等しいときにアイテム名で比較するようにしておくと、結果が安定します。

実装プログラム

以下は、この解法の動作を示すC++プログラムです。

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

bool compVal(pair<string, int> A, pair<string, int> B) {

    if (A.second == B.second)
        return A.first < B.first;
    return A.second < B.second;
}

int main() {

    int k = 2;
    int n = 3;
    vector<pair<string, int> > items;
    items.push_back(make_pair("item1", 350));
    items.push_back(make_pair("item2", 150));
    items.push_back(make_pair("item3", 500));
    items.push_back(make_pair("item4", 100));

    sort(items.begin(), items.end(), compVal);
    
    cout<<k<<" items with least value are \n";
    for (int i = 0; i < min(n, k); ++i)
        cout<<"Item : "<<items[i].first<<", value : "<<items[i].second<<endl;
    return 0;
}

実行結果

2 items with least value are
Item : item4, value : 100
Item : item2, value : 150

まとめ

このように、リストを値の昇順にソートして先頭の k 個を取得するだけで、値が最も小さい k 個のアイテムを簡単に求められます。計算量はソートに依存し、O(n log n) となります。データ数が非常に多い場合は、優先度付きキュー（ヒープ）を使うことで O(n log k) まで効率化できるので、状況に応じて使い分けるとよいでしょう。