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個の最小値のアイテムが見つかります。

ソリューションの動作を説明するプログラム

例

#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