C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++での高さによるキューの再構築

列に並んでいる人のランダムなリストがあると考えてください。各人が整数のペア（h、k）で記述されている場合、ここでhは身長、kは彼の前にいるh以上の身長を持つ人の数です。キューを再構築するための1つのメソッドを定義する必要があります。したがって、指定された配列が[[7,0]、[4,4]、[7,1]、[5,0]、[6,1]、[5,2]]の場合、出力は次のようになります。 [[5,0]、[7,0]、[5,2]、[6,1]、[4,4]、[7,1]]

これを解決するには、次の手順に従います-

  • 次の比較戦略に基づいて、指定されたアレイを並べ替えます
    • a [0] =b [0]の場合は、a [1]> b [1]を返します。それ以外の場合は、a [0] を返します。
  • ansと呼ばれる1つのベクトルを作成します
  • 指定された配列の範囲サイズが0までのiの場合
    • （ans + p [i、1]、p [i]の最初の要素）をans配列に挿入します
  • 回答を返す
例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
bool cmp(vector <int> a, vector <int> b){
   if(a[0] == b[0])return a[1] > b[1];
      return a[0] < b[0];
}
class Solution {
public:
   vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
      sort(p.begin(), p.end(), cmp);
      vector < vector <int> > ans;
      for(int i = p.size()-1; i>=0; i--){
         ans.insert(ans.begin() + p[i][1], p[i]);
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
   print_vector(ob.reconstructQueue(v));
}

入力

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

出力

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

  1. C++でのベクトルの並べ替え

    C ++でのベクトルの並べ替えは、std ::sort（）を使用して実行できます。 ヘッダーで定義されています。安定したソートを取得するには、std::stable_sortを使用します。これはsort（）とまったく同じですが、等しい要素の相対的な順序を維持します。必要に応じて、Quicksort（）、mergesort（）も使用できます。 アルゴリズム Begin    Decalre v of vector type.       Initialize some values into v in array pattern.  

  2. C ++でベクトルを初期化する方法は？

    初期化ベクトルはさまざまな方法で実行できます 1）push_back（）メソッドでベクトルを初期化します アルゴリズム Begin    Declare v of vector type.    Call push_back() function to insert values into vector v.    Print “Vector elements:”.    for (int a : v)       print all the elements