数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学通过追加和在中间插入MEX形成的序列中第k个索引的值
在这篇文章中，我们将学习MEX，并将生成C++代码，该代码使用在给定序列上执行追加和MEX（>0）操作形成的序列返回第k个索引。
要执行的操作路线图如下所示：
从仅包含数字1的序列开始，即[1]。
现在，我们需要执行(n-1)个步骤：
在每个步骤中，我们通过自身追加当前序列。例如，如果现有序列是[1, 2, 3]，追加后它将变为[1, 2, 3, 1, 2, 3]。
现在，找到序列的最小排除值，即(MEX)。这是序列中未出现的最小正整数。因此，此序列的MEX是-4。
将MEX值插入序列的中间。这意味着将其放置在序列的两半之间。例如，如果序列是[1, 2, 3, 1, 2, 3]，MEX是4，则插入MEX后生成的序列变为[1, 2, 3, 4, 1, 2, 3]。
重复这些步骤，直到完成(n-1)个步骤。执行所有步骤后，我们将得到结果序列。
我们的目标是确定现有序列中第k个索引处存在的整数。我们可以简单地访问序列的第k个索引以找到所需输出。
方法1：暴力方法
对此的第一种也是暴力方法是：只需遵循问题陈述中给出的所有步骤，最后返回所需的索引。
示例
下面给出了使用C++实现此暴力方法的代码。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int find_mex(vector<int>& seq) {
int mex = 1;
while (find(seq.begin(), seq.end(), mex) != seq.end()) {
mex++;
}
return mex;
}
int find_value(int number, int index) {
vector<int> seq = {1};
int iterator = 1;
for (iterator = 1; iterator < number ; iterator++){
int mex = find_mex(seq);
seq.insert(seq.end(), seq.begin(), seq.end());
seq.insert(seq.begin() + seq.size() / 2, mex);
}
return seq[index - 1];
}
int main(){
int number = 4;
int index = 8;
int result = find_value(number , index);
cout << "The value at index " << index << " after " << number << " steps is: " << result << endl;
return 0;
}
输出
The value at index 8 after 4 steps is: 4
时间复杂度 - 上述代码实现的时间复杂度为二次方，表示为O(n^2)，这是由于find_value和find_mex函数的嵌套执行。
空间复杂度 - 上述方法实现所需的辅助空间也是O(n^2)，因为序列在每次迭代中追加自身时大小呈指数增长。
方法2：二分查找方法
另一种可以使用的方法是二分查找方法。可以观察到，结果序列中间的元素始终等于n。序列的长度为2n - 1，其中序列的长度遵循模式(1, 3, 7, 15, ..., 2n - 1)。
我们可以应用二分查找来有效地解决这个问题。我们从第n步开始搜索，并将中间的索引与k的值进行比较。如果中间索引等于k，我们返回n，因为第n步的中间元素本身就是n。如果中间索引不等于k，我们将根据k的值更新我们的搜索范围。如果k大于中间的索引，我们继续在范围的后半部分搜索；否则，我们在前半部分搜索。
我们将重复此过程，直到找到索引k。在每次迭代中，我们将n的值减1，然后相应地更新我们的搜索。
示例
下面给出了使用C++实现此方法的代码。
#include <bits/stdc++.h>
using namespace std;
int getIndex(int number , int index){
int middle_element = number ;
int l = 1;
int r = pow(2, number) - 1;
while (1) {
int middle = (l + r) / 2;
if (index == middle) {
return middle_element;
break;
}
middle_element--;
if (index < middle)
r = middle - 1;
else
l = middle + 1;
}
}
int main(){
int number = 4;
int index = 8;
int result = getIndex(number , index);
cout << "The value at index " << index << " after " << number << " steps is: " << result << endl;
return 0;
}
输出
The value at index 8 after 4 steps is: 4
时间复杂度 - 因为我们在此方法中使用二分查找，所以时间复杂度将降低到O(log(n))
空间复杂度 - 此方法所需的额外空间保持不变，与输入大小无关，复杂度为O(1)。
结论
我们讨论了两种不同的方法来解决给定的问题，第一种方法是基本暴力方法，其中由于时间复杂度为O(n^2)，因此第一种方法效率不高。后来，我们实现了二分查找方法，将解决方案的时间复杂度降低到O(log(n))，这在比较中非常有效。我们还将空间复杂度降低到常数空间。
52 次浏览
