在C ++中使给定集合的MEX等于x的最小操作

问题陈述

给定一组n个整数，请执行最少数量的操作（可以将元素插入到集合中或从集合中删除元素），以使集合的MEX等于x（给定）。

注–一组整数的MEX是其中不存在的最小非负整数。例如，集合{0，2，4}的MEX为1，集合{1,2，3}的MEX为0

示例

如果n = 5且x = 3且数组为{0，4，5，6，7}，则我们需要最少2次运算

算法

• 这种方法是在最终集中看到小于x的所有元素都应该存在，x不应该存在，大于x的任何元素都没有关系。

• 因此，我们将计算初始集中不存在的少于x个元素的数量，并将其添加到答案中。

• 如果x存在，我们将在答案中加1，因为x应该被删除。

示例

#include <iostream>
using namespace std;
int getMinOperations(int *arr, int n, int x) {
   int k = x, i = 0;
   while (n--) {
      if (arr[n] < x) {
         --k;
      }
      if (arr[n] == x) {
         ++k;
      }  
   }
   return k;
}
int main() {
   int arr[] = {0, 4, 5, 6, 7};
   int n = sizeof(arr) / sizeof(arr[0]); int x = 3;
   cout << "Minimum required operations = " << getMinOperations(arr, n, x) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Minimum required operations = 2