資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在C++中查詢包含所有元素（按相同順序）的最小子陣列
假設我們有兩個大小分別為m和n的陣列，任務是在第一個陣列中找到包含第二個陣列所有元素的最小長度子陣列。第二個陣列中的元素可能以非連續的方式出現在較大的陣列中，但順序必須相同。例如，如果兩個陣列是A = [2, 2, 4, 5, 8, 9]和B = [2, 5, 9]，則輸出將為5。因為A的最小子陣列將是[2, 4, 5, 8, 9]。這裡所有元素[2, 5, 9]都按相同的順序排列。所以大小是5。
我們可以透過檢查第一個元素是否與第二個陣列的第一個元素匹配來解決這個問題。當第一個元素匹配時，我們在主陣列中匹配第二個陣列的其餘元素，當所有元素都匹配時，根據需要更新長度。完成此操作後，返回子陣列的最小長度。
示例
#include<iostream>
using namespace std;
int lengthMinSubarray(int A[], int n, int B[], int m) {
int res = INT_MAX;
for (int i = 0; i < n - m + 1; i++) {
if (A[i] == B[0]) {
int j = 0, idx = i;
for (; idx < n; idx++) {
if (A[idx] == B[j])
j++;
if (j == m)
break;
}
if (j == m && res > idx - i + 1)
res = (idx == n) ? idx - i : idx - i + 1;
}
}
return res;
}
int main() {
int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
int B[] = { 5, 5, 7 };
int n = sizeof(A)/sizeof(A[0]);
int m = sizeof(B)/sizeof(B[0]);
cout << "Minimum length of subarray: " << lengthMinSubarray(A, n, B, m);
}輸出
Minimum length of subarray: 3
更新於：2019年12月19日
240 次瀏覽
廣告