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

C++で同じ順序ですべての要素を含む最小のサブ配列を検索します


サイズmとnの2つの配列があるとします。タスクは、最初の配列で最小長のサブ配列を見つけることです。これには、2番目の配列の場合はすべての要素が含まれます。 2番目の配列の要素は、大きな配列に連続していない場合がありますが、順序は同じである必要があります。したがって、2つの配列がA =[2、2、4、5、8、9]、B =[2、5、9]の場合、出力は5になります。Aの最小のサブ配列として、は[ 2、4、5、8、9]。ここでは、[2、5、9]のようなすべての要素が同じ順序になっています。したがって、サイズは5です。

これは、最初の要素が2番目の配列の最初の要素と一致することを確認することで解決できます。最初の要素が一致したら、メイン配列の2番目の配列の残りの要素と一致し、すべての要素が一致したら、必要に応じて長さを更新します。これを行った後、サブアレイの最小長を返します。

#include<iostream>
using namespace std;
int lengthMinSubarray(int A[], int n, int B[], int m) {
   int res = INT_MAX;
   for (int i = 0; i < n - m + 1; i++) {
      if (A[i] == B[0]) {
         int j = 0, idx = i;
         for (; idx < n; idx++) {
            if (A[idx] == B[j])
               j++;
            if (j == m)
               break;
         }
         if (j == m && res > idx - i + 1)
         res = (idx == n) ? idx - i : idx - i + 1;
      }
   }
   return res;
}
int main() {
   int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
   int B[] = { 5, 5, 7 };
   int n = sizeof(A)/sizeof(A[0]);
   int m = sizeof(B)/sizeof(B[0]);
   cout << "Minimum length of subarray: " << lengthMinSubarray(A, n, B, m);
}

出力

Minimum length of subarray: 3

  1. C++を使用してすべての要素が割り切れるような配列要素を見つけます

    要素が少ない配列Aがあるとします。すべての要素をそれで分割できるように、Aから要素を見つける必要があります。 Aが[15、21、69、33、3、72、81]のようであるとすると、すべての数値は3で割り切れる可能性があるため、要素は3になります。 この問題を解決するために、Aの最小の数値を取得し、すべての数値を最小の数値で除算できるかどうかを確認します。はいの場合は数値を返し、そうでない場合はfalseを返します。 例 #include<iostream> #include<algorithm> using namespace std; int getNumber(in

  2. C++で配列のすべての要素を同じにするための最小限の削除操作。

    問題の説明 要素が繰り返されるようなn個の要素の配列が与えられます。配列から任意の数の要素を削除できます。タスクは、配列から削除する要素の最小数を見つけて、配列を等しくすることです。 arr[] = {10, 8, 10, 7, 10, -1, -4, 12} すべての配列要素を同じにするには、強調表示された5つの要素を削除する必要があります。 アルゴリズム 1. Count frequency of each element 2. Find maximum frequecy among the frequencies. Let us call this as maxFrequncy 3.