使用 C++ 计算两个数组中的元素

Z时代
2024-01-10
分类：综合

让我们假设我们已经给出了两个未排序的数组 arr1[] 和 arr2[]。任务是计算 arr2[] 中元素的总数，其中 arr1[] 的每个元素都小于或等于 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) 将两个数组及其大小作为输入，并返回 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;
}