数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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
更新于: 2019-11-22
492 次查看
广告