資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告