資料結構
網路
關係資料庫管理系統 (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 次瀏覽
