資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中每個大小為 K 的子陣列中的最大唯一元素
在這個問題中，我們給定一個整數陣列和一個整數 K。我們的任務是建立一個程式，該程式將找到每個大小為 K 的子陣列中的最大唯一元素，並且沒有重複。
讓我們舉個例子來理解這個問題，
輸入 -
array = {4, 1, 1, 3, 3}
k = 3輸出 -
4 3 1
解釋 -
Sub-array of size 3
Subarray {4, 1, 1}, max = 4
Subarray {1, 1, 3}, max = 3
Subarray {1, 3, 3}, max = 1為了解決這個問題，一個簡單的方法是執行兩個迴圈並建立子陣列，找到不同的元素並列印其中的最大值。
但一個有效的解決方案是使用滑動視窗方法，使用雜湊表和自平衡 BST 來查詢最大元素。
因此，我們將遍歷陣列，對於長度為 k 的摘要，將元素的計數儲存在雜湊表中，並將元素儲存在集合中（它將僅儲存唯一元素）。並列印集合中的最大值，並在陣列的每次迭代中執行相同的操作。
示例
程式說明我們解決方案的工作原理，
#include <bits/stdc++.h>
using namespace std;
void maxUniqueSubArrayElement(int A[], int N, int K){
map<int, int> eleCount;
for (int i = 0; i < K - 1; i++)
eleCount[A[i]]++;
set<int> uniqueMax;
for (auto x : eleCount)
if (x.second == 1)
uniqueMax.insert(x.first);
for (int i = K - 1; i < N; i++) {
eleCount[A[i]]++;
if (eleCount[A[i]] == 1)
uniqueMax.insert(A[i]);
else
uniqueMax.erase(A[i]);
if (uniqueMax.size() == 0)
cout<<"-1\t" ;
else
cout<<*uniqueMax.rbegin()<<"\t";
int x = A[i - K + 1];
eleCount[x]--;
if (eleCount[x] == 1)
uniqueMax.insert(x);
if (eleCount[x] == 0)
uniqueMax.erase(x);
}
}
int main(){
int a[] = { 4, 3, 2, 2, 3, 5};
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
cout<<"The maximum unique element for a subarray of size "<<k<<" is\n";
maxUniqueSubArrayElement(a, n, k);
return 0;
}輸出
The maximum unique element for a subarray of size 4 is 4 -1 5
更新於: 2020-06-03
234 次檢視
廣告