C++を使用して2つの配列の要素をカウントする

ソートされていない2つの配列arr1[]とarr2[]を指定したと仮定します。タスクは、arr1[]の各要素がarr2[]に存在する要素以下であるarr2[]の要素の総数をカウントすることです。ただし、両方の配列の要素にも重複が含まれている可能性があります。

たとえば、

入力-1 −

N = 6
M = 7
arr1[N] = {1, 2, 5, 0, 6, 3}
arr2[M] = {0,0,1,2,1,3,4,6,8}

出力 −

4 5 7 2 8 6

この問題を解決するために使用されるアプローチ

arr1 []のすべての要素をカウントし、それらがarr2 []の要素以下であるかどうかを確認するには、arr2 []を並べ替え、バイナリ検索メソッドを使用して、より少ないarr1[]の要素を見つけます。またはarr2[]に存在する要素と等しい。

• arr1とarr1のサイズを「m」と「n」として入力します。

• 配列要素を入力します。

• 関数countInSecond（int * arr1、int * arr2、int m、int n）は、2つの配列とそのサイズを入力として受け取り、arr2[]に存在する要素の数を返します。

• arr2[]を並べ替えます。

• arr1 []を繰り返し処理し、バイナリ検索を使用してarr2[]内の特定の要素を見つけます。

• 以下の要素の数を返します。

例

#include <bits/stdc++.h>
using namespace std;
void countInSecond(int *nums1,int *nums2,int m,int n){
   sort(nums2, nums2+n);
   int i=0;
   for(int i=0;i<m;i++){
      int s=0;
      int e=n-1;
      while(s<=e){
         int mid= (s+e)/2;
         if(nums2[mid]<=nums1[i])
            s= mid+1;
         else
            e= mid-1;
      }
      cout<<e+1<<" ";
   }
}
int main(){
   int m=6;
   int n=9;
   int arr1[m]={1,2,5,0,6,3};
   int arr2[n]= {0,0,1,2,1,3,4,6,8};
   countInSecond(arr1,arr2,m,n);
   return 0;
}

出力

上記のコードを実行すると、次のように出力が生成されます

4 5 7 2 8 6

arr2の要素以下であるarr1のすべての要素の数は、{4 5 7 286}です。