在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