C++ 中达到给定 MEX 的最小增量

2024 年 8 月 29 日 | 阅读 16 分钟

在 C++ 中，也存在一种情况，即需要通过最少的增量来找到数组中最小排除值 (MEX)。MEX 通常查找数组元素中不存在的最小非负整数。本指令的最终目的是生成一个数组，该数组以最少的增量包含给定 MEX 值的所有非负整数。

这可以通过执行排序和二分查找操作来完成。首先对数组进行排序。最后，使用二分查找来找到排序数组中 MEX 的位置。找到的MEX与其位置之间的时间差即可得到可以计算的最小步数。此方法可以构建数组。同时，该方法允许 MEX 标准是最优的，并且具有O(N)时间复杂度。

MEX（最小排除值）

MEX 是数组中不存在的最小非负整数。

问题在于增量将使数组包含从 0 到指定 MEX 的整数。

最小增量

此处将“增量”定义为将数组元素的值增加 1。

目标是找到完成目标 MEX 所需的最少增量。

方法 1：使用排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Function to calculate the minimum increments to reach the given MEX
int minIncrementsToMex(const vector<int>& nums, int mex) {
    // Step 1: Sort the array
    vector<int> sorted_nums = nums;
    sort(sorted_nums.begin(), sorted_nums.end());
    // Step 2: Initialize variables for tracking increments and current MEX
    int increments = 0;
    int current_mex = 0;  // Initialize current MEX
    // Step 3: Iterate through the sorted array
    for (int i = 0; i < sorted_nums.size(); ++i) {
        // Step 3a: Check if the element is equal to the current MEX
        if (sorted_nums[i] == current_mex) {
            // If yes, move to the next MEX
            current_mex++;
        } else if (sorted_nums[i] > current_mex) {
            // Step 3b: If the element is greater than the current MEX,
            // increment the current MEX and add the difference to increments
            current_mex++;
            increments += (current_mex - sorted_nums[i]);
        }
        // If the element is less than the current MEX, it's already processed
        // and doesn't require an increment.
    }
    // Step 4: Handle remaining MEX values after the sorted array ends
    increments += (mex - current_mex);
    // Step 5: Return the total increments
    return increments;
}
int main() {
    // Example usage
    vector<int> nums = {1, 3, 2, 5};
    int mex = 4;
    // Step 6: Call the Function to get the result
    int result = minIncrementsToMex(nums, mex);
    // Step 7: Output the result
    cout << "Original Array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    cout << "Minimum increments required to reach MEX " << mex << ": " << result << endl;
    // Step 8: Return from main Function
    return 0;
}

输出

Original Array: 1 3 2 5 
Minimum increments required to reach MEX 4: 0

说明

提供的 C++ 源代码解决了在给定列表中获得预定义的 MEX（最小排除值）所需最少增量的问题。它通过对数组进行排序并在每次迭代中查找最小值来做到这一点。

排序数组

首先将原始数组（nums）的元素复制到一个新向量（sorted_nums）中，然后使用 sort() 对该向量进行排序，使其按升序排列。排序是数组元素遍历中的关键操作。

跟踪变量

使用两个变量来跟踪数组的进度和进行的增量：

增量 (Increments): 设置为 0，此变量累加进行的增量数。

当前 MEX (Current_mex): 代表迭代中数组值的当前 MEX，初始值为零。

迭代遍历排序后的数组

循环遍历排序后的数组（sorted_nums）。在每次迭代中，代码会检查当前元素与当前 MEX 之间的关系。

因此，如果元素等于当前 MEX，则表示我们已找到 MEX，代码会将 current_me[x] 递增以移动到下一个 MEX。

假设元素大于当前 MEX；代码会增加当前 MEX，并将总增量加上MEX和元素之间的绝对差。这就是为什么数组以牺牲性能为代价用连续整数填充的原因。

处理剩余的 MEX 值

对数组进行排序后，下一步是将 MEX 与连续值进行比较并填充。因此，它从已处理的最后一个 MEX 数字中减去指定的 MEX。然后将此差值添加到总增量中。

返回结果

该函数返回总补数，该补数反映了达到指定 MEX 所需的最少补数。

Main 中的示例用法

main 函数通过考虑给定的数组（nums）和预定的 MEX 值来演示算法的用法。它使用这些参数调用minIncrementsToMex 函数并返回结果。

该程序显示原始数组以及实现所需 MEX 所需的最小跳数。这有助于用户了解数组的变化如何满足MEX 条件。

复杂度分析

可以观察所提供 C++ 代码的时间和空间复杂度，以确定将 MEX 提高到目标值的最小增量，从而了解其有效性。

时间复杂度

时间复杂度取决于数据排序的方式。在 C++标准模板库 (STL)中，sort 函数的平均时间性能为O(n log n)，其中 'n' 代表输入数组的大小。

排序数组

sort 操作对长度为 'n' 的数组 sorted_nums 进行排序。排序算法的复杂度为O(n log n)。

排序后，算法会遍历数组一次。每次迭代都包含一个常数时间操作，包括比较和增量。因此，此步骤的总时间复杂度为O(n)。

处理剩余的 MEX 值

最后一个步骤，处理剩余的 MEX 值，也包括常数时间操作，因此为整体时间复杂度增加了O(1)。

总时间复杂度取决于领先项，即排序过程。因此，代码的整体时间复杂度为O(n log n)。

空间复杂度分析

代码的空间复杂度受算法执行期间动态创建和使用的数据结构的影响。

排序数组 (sorted_nums)

因此，创建了一个新向量 sorted_nums 来存储原始数组的排序版本。该向量的空间复杂度为O(n)，其中 'n' 是输入数组的大小。

跟踪变量 (increments 和 current_mex)

使用两个变量（increments 和 current_mex）来跟踪增量和当前 MEX。这些变量具有恒定的空间要求，对空间复杂度贡献O(1)。

其他局部变量

代码使用一些其他局部变量，如循环计数器和临时变量，它们占用恒定空间，并对整体空间复杂度贡献O(1)。

空间复杂度中的主导项是排序数组所需的空间。因此，代码的整体空间复杂度为O(n)。

方法 2：使用计数数组

#include <iostream>
#include <vector>
using namespace std;
//Function to calculate the minimum increments to reach the given MEX using a counting array
int minIncrementsToMex(const vector<int>& nums, int mex) {
    // Check for invalid input conditions
    if (mex < 0) {
        // Return -1 for invalid MEX
        return -1;
    }
    // Step 1: Create a Counting Array
    // The counting array will keep track of the occurrences of each integer
    // The size of the counting array is determined by the specified MEX value
    vector<int> count(mex + 1, 0);
    // Step 2: Count Occurrences in Original Array
    // Iterate through the original array and update the counting array
    // with the occurrences of each integer (up to the specified MEX)
    for (int num : nums) {
        if (num <= mex) {
            count[num]++;
        }
    }
    // Step 3: Iterate Through Counting Array
    // Initialize variables for tracking increments and the current MEX
    int current_mex = 0;
    int increments = 0;
    // Iterate through the counting array to identify gaps and make increments
    for (int i = 0; i <= mex; ++i) {
        // Check if the current index represents a gap
        // If count[i] is greater than 0, it means the integer i is present in the array
        // If i is greater than the current MEX, make increments to fill the gap
        while (count[i] > 0 && i > current_mex) {
            current_mex++;
            increments += (current_mex - i);
        }
    }
    // Return the total increments
    return increments;
}
int main() {
    // Example usage
    vector<int> nums = {1, 3, 2, 5};
    int mex = 4;
    // Call the Function to get the result
    int result = minIncrementsToMex(nums, mex);
    //Output the result
    cout << "Original Array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    // Display the result
    cout << "Minimum increments required to reach MEX " << mex << ": " << result << endl;
    // Return from main Function
    return 0;
}

输出

Original Array: 1 3 2 5 
Minimum increments required to reach MEX 4: 0

说明

提供的 C++ 代码旨在利用计数数组方法找出数组中获得特定 MEX 元素所需的最少添加次数。

初始化计数数组 (count)

首先，将准备一个大小为MEX + 1的计数数组（count），其中 MEX 代表 MEX 值。此数组存储MEX以下所有整数的出现次数。

计算原始数组（nums）中的出现次数

代码遍历原始数组（nums）的每个元素，并使用每个数字的出现次数更新计数数组。此步骤确保了每个整数的出现次数计数直到其关联的 MEX。

迭代遍历计数数组

初始化两个变量：文本值 current_mex 用于跟踪MEX值，increments 用于跟踪进行的增量总数。因此，遍历计数数组。对于所有索引，代码会尝试查找当前 MEX 和索引之间是否存在间隙。如果间隙意味着缺少某些整数，则会进行一系列增量来填补这些间隙。将现有 MEX 与索引之间的差值添加到所有增量中。

返回总增量

该函数返回总增量，即最初达到 MEX 所需的最少增量数。

错误处理

无效输入处理

代码包含对无效输入的检查。如果指定的 MEX 值是负数，则函数返回 -1。这表明 MEX 值无效。

Main 中的示例用法

主函数展示了如何在具有指定 MEX 值的数组（nums）上实现算法。使用这些参数调用此函数，并通过打印获得输出。

输出显示

该程序显示了初始数组以及达到目标 MEX所需的最小增加操作数。否则，如果 MEX 不可达或输入无效，则会显示适当的消息。

复杂度分析

我们可以计算给定 C++ 代码的执行时间和内存消耗来评估其性能。

时间复杂度分析

决定算法复杂度的主要因素是遍历初始数组（nums）以及随后遍历计数数组的迭代。

计算原始数组中的出现次数

最内层循环将遍历原始数组（nums），其时间复杂度为O(n)，其中 'n' 是数组的长度。

迭代遍历计数数组

在第二个循环中，循环变量遍历大小为 MEX + 1 的计数数组。在最坏的情况下，此循环运行需要 'MEX' 次迭代。因此，此循环的时间复杂度为O(MEX)。

通过合并这两个步骤，代码的时间复杂度为O(n + MEX)。当 'MEX' 远小于 'n' 时，'n' 是主导项，因此时间复杂度缩短为O(n)。

空间复杂度分析

额外的内存消耗由创建的额外数据结构决定。

计数数组 (count)

计数数组（count）占用的空间为O(MEX + 1)。它与特定的 MEX 值相关。因此，空间复杂度为O(mex)。

跟踪变量 (current_mex 和 increments)

这里使用两个整数变量（current_mex 和 increments）来跟踪数组的进度和进行的增量。这些变量是恒定空间，其余O(1)用于空间复杂度。

其他局部变量

代码还使用了一些其他局部变量，如循环计数器和临时变量，它们使用O(1)恒定空间并贡献于整体空间复杂度。

方法 3：使用 HashSet

A HashSet is a data structure that allows for constant-time average case complexity for basic operations such as insertion, deletion, and lookup.
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
//Function to calculate the minimum increments to reach the given MEX using a HashSet
int minIncrementsToMex(const vector<int>& nums, int mex) {
    // Step 1: HashSet Initialization
    unordered_set<int> seen;
    // Step 2: Count Occurrences in Original Array
    for (int num : nums) {
        seen.insert(num);
    }
    // Step 3: Iterate to Find the MEX
    while (seen.count(mex)) {
        mex++;
    }
    // Step 4: Return Total Increments
    return mex - seen.size();
}
int main() {
    // Example usage
    vector<int> nums = {1, 3, 2, 5};
    // Input the desired MEX value
    int desiredMex;
    cout << "Enter the desired MEX value: ";
    cin >> desiredMex;
    // Call the Function to get the result
    int result = minIncrementsToMex(nums, desiredMex);
    //Output the result
    cout << "Original Array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    // Display the result
    cout << "Minimum increments required to reach MEX " << desiredMex << ": " << result << endl;
    // Return from main Function
    return 0;
}

输出

Enter the desired MEX value: 4
Original Array: 1 3 2 5 
Minimum increments required to reach MEX 4: 0

说明

提供的 C++ 代码通过利用 HashSet 数据结构来计算获得数组中所需MEX（最小排除值）所需的最小增量数，该数据结构可以快速跟踪数组中的唯一元素并导出最小的缺失非负整数。

HashSet 初始化

处理过程从使用 C++ STL unordered_set创建名为"seen"的 HashSet 开始。在这种情况下，HashSet 负责存储数组中存在的唯一元素。

计算原始数组中的出现次数

循环遍历原始数组（nums 数组），将每个元素添加到“seen”中。这保证了“seen”字典将包含初始数组中的所有唯一元素，从而便于识别哪些整数已在数组中，哪些缺失。

迭代查找 MEX

计算出原始数组中每个元素重复的次数后，将一个名为 'mex' 的变量初始化为 0。目的是找出最小排除值，即数组中不存在的最小非负整数。为了检查，迭代地使用 while 循环检查当前 'mex' 值是否存在于 HashSet 中。如果找到，则会增加 'mex'，直到获得一个不在数组中的值。

返回总增量

当循环找到MEX 值时，函数返回实现该 MEX 的总最小化。这是通过找到最终的 'mex' 值与 'seen' HashSet 的大小之间的差值来计算的，该 HashSet 包含初始数组中的唯一元素数。

所需的 MEX 的用户输入

main 函数要求用户输入 ME 值。'desiredMex'变量被赋值为输入值。因此，在修改后调用 `minIncrementsToMex` 函数，并将输入（nums）和用户的 MEX 值作为参数。

输出显示

该程序生成原始数组以及指定 MEX 所需的最小更新。它包括一个循环来输出原始数组的每个元素。通过说明获得目标 MEX 值所需的最小增加次数，将结果显示给用户。

复杂度分析

可以分析提供的 C++ 代码的时间和空间复杂度，以了解其在执行期间的资源利用效率。

时间复杂度分析

代码的时间复杂度是通过遍历原始数组、更新 HashSet 和查找 MEX 的循环中的操作来计算的。

HashSet 初始化和计数出现次数：声明 unordered_set 并遍历原始数组需要O(n)时间。这是因为数组中的所有元素都必须处理一次。

查找 MEX：顺序查找 MEX 的 while 循环的运行时取决于MEX的值。在最坏的情况下，当 MEX 大于数组大小时，时间复杂度为O(mex)，其中 'mex' 是我们想要的 MEX 值。

总的来说，代码的时间复杂度通常由O(n)项决定，在最坏情况下为O(n + mex)。

空间复杂度分析

程序空间复杂度取决于运行时创建的附加数据结构。

HashSet (seen): HashSet 'seen' 用于跟踪原始数组中遇到的唯一对象。最多，如果所有元素都不同，HashSet 的大小将是 'n'，即输入数组的大小。因此，HashSet 的空间复杂度为O(n)。

变量 (mex): 'mex' 等变量的空间使用是恒定的，因此对空间复杂度贡献O(1)。

用户输入：用户输入的空间占用是恒定的，不取决于输入数组的大小。

计算所有这些参数后，程序的时间复杂度为O(n)。

方法 4：使用二分查找算法

另一种方法基于二分查找，也可以用于在排序数组中查找 MEX。此方法执行二分查找以检查初始猜测，对数组进行排序，然后返回最小的缺失非负整数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Function to calculate the minimum increments to reach the given MEX using Binary Search
int minIncrementsToMex(const vector<int>& nums) {
    // Step 1: Sort the array
    vector<int> sortedNums(nums.begin(), nums.end());
    sort(sortedNums.begin(), sortedNums.end());
    // Step 2: Binary Search for MEX
    int low = 0, high = sortedNums.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (sortedNums[mid] > mid) {
            // Missing element is on the left side
            high = mid;
        } else {
            // Missing element is on the right side
            low = mid + 1;
        }
    }
    // 'low' now represents the position of the MEX
    // Step 3: Calculate Increments
    int mex = low;
    int increments = mex;
    return increments;
}
int main() {
    // Example usage
    vector<int> nums = {1, 3, 2, 5};
    // Call the Function to get the result
    int result = minIncrementsToMex(nums);
    //Output the result
    cout << "Original Array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    //Output the sorted array
    cout << "Sorted Array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    // Display the result
    cout << "Minimum increments required to reach MEX: " << result << endl;
    // Return from the main Function
    return 0;
}

输出

Original Array: 1 3 2 5 
Sorted Array: 1 3 2 5 
Minimum increments required to reach MEX: 0

说明

使用二分查找技术，这里的 C++ 代码旨在计算达到给定数组中指定的最小排除值 (MEX) 所需的最少增量。

minIncrementsToMex 函数

排序数组

首先，函数复制原始数组，然后使用 C++ STL 的 sort 函数将其按非递减顺序排序。

二分查找 MEX

然后设置两个指针 'low' 和 'high' 来指定数组中的搜索范围。函数执行二分查找，直到'low' 指针大于等于'high' 指针。在每次迭代中，它计算中间索引，然后将该索引处的值与索引本身进行比较。根据比较结果，它根据结果将搜索范围缩小到左侧或右侧。

计算增量

完成二分查找后，函数标识 MEX 值并计算实现该值所需的最小增量。'mex'变量包含已标识的 MEX，而 'increments' 存储结果。

主函数

展示函数演示了minIncrementsToMex 函数的用法，其中包含一个示例数组。程序显示原始数组和排序后的数组，以及实现所需 MEX 所需的最少步骤。

代码执行

对原始数组进行排序：原始数组是 {1, 3, 2, 5}，并打印其排序版本。

二分查找和计算增量：二分查找在排序数组中给出 MEX 的索引，并确定MEX 值和增量。

输出显示：最后，将原始数组和排序后的数组以及最小增量作为最终结果打印出来。

复杂度分析

时间复杂度分析

排序数组

代码使用 C++ STL 的 sort 函数对输入数组进行排序。通常，排序顺序为O(n log n)，其中 'n' 代表数组大小。

二分查找 MEX

对排序后的数组应用二分查找算法来查找MEX 值。二分查找运行时间为O(log n)，其中 n 是排序后数组的大小。这是因为搜索空间在每次迭代中都会减半，直到找到目标值。

最后，排序是时间复杂度的最重要因素。因此，代码的时间复杂度为O(n log n)。

空间复杂度分析

排序数组 (sortedNums)

初始化了一个新向量sortedNums来保存输入数组的排序版本。此操作的空间复杂度取决于所选择的排序算法。如果使用就地排序算法，则其空间复杂度为 O(1)，因为它在相同的内存空间中对数组进行排序。此外，排序所需的额外内存可能在最坏情况下为O(n)。

变量 (low, high, mid, mex, increments)

这些变量的大小是恒定的，并对空间复杂度贡献O(1)。

输入数组 (nums)

输入数组被保留，没有使用额外的空间。

考虑到这些因素，如果排序使用了额外的内存，则代码的最坏情况空间复杂度为 O(n)。如果使用了就地排序算法，则空间复杂度可以为O(1)。

下一个主题C++ 中键入给定字符串所需的最少按键次数

← 上一个下一个 →

C++ 中达到给定 MEX 的最小增量

MEX（最小排除值）

最小增量

方法 1：使用排序

方法 2：使用计数数组

方法 3：使用 HashSet

方法 4：使用二分查找算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中达到给定 MEX 的最小增量

MEX（最小排除值）

最小增量

方法 1：使用排序

方法 2：使用计数数组

方法 3：使用 HashSet

方法 4：使用二分查找算法

相关帖子

C++ 中 std::set::lower_bound 和 std::lower_bound 的区别

C++ 活动选择问题

Needleman-Wunsch 算法

C++ 中预期的非限定 id 错误

C++ auto_ptr

C++ STL 中的数组求和

C++ 对象指针

初学者最佳 C++ 游戏引擎

C++ 二分查找

编写 C++ 程序实现 Bloom 过滤器数据结构

订阅 Tpoint Tech

联系信息

关注我们

教程