資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中具有 K 個不同整數的子陣列
假設我們有一個包含正整數的陣列 A，如果該子陣列中不同整數的數量正好為 K，則可以稱 A 的一個好的子陣列（連續的）為好子陣列。因此，如果陣列類似於 [1,2,3,1,2]，則有 3 個不同的整數：1、2 和 3。我們必須找到 A 的好子陣列的數量。
因此，如果輸入類似於 [1,2,3,1,4] 且 K = 3，則輸出將為 4，因為它可以形成三個具有恰好四個不同整數的子陣列，它們是 [1,2,3]、[1,2,3,1]、[2,3,1]、[3,1,4]。
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 atMost()，它將接收一個數組 a 和變數 k，
定義一個集合 current
j := 0，ans := 0，n := a 的大小
定義一個對映 m
對於初始化 i := 0，當 i < a 的大小，更新（將 i 增加 1），執行 -
如果 m[a[i]] 為零，則將 m[a[i]] 增加 1 -
當 k < 0 時，執行 -
如果將 m[a[j]] 減少 1 且 m[a[i]] 為零，則 -
(將 k 增加 1)
(將 j 增加 1)
x := ((i - j) + 1)
ans := ans + x
返回 ans
從主方法執行以下操作 -
返回 atMost(a, k) - atMost(a, k - 1);
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraysWithKDistinct(vector<int>& a, int k) {
return atMost(a, k) - atMost(a, k - 1);
}
int atMost(vector <int>& a, int k){
set <int> current;
int j = 0;
int ans = 0;
int n = a.size();
unordered_map <int, int> m;
for(int i = 0; i < a.size(); i++){
if(!m[a[i]]++) k--;
while(k < 0){
if(!--m[a[j]])
k++;
j++;
}
int x = ((i - j) + 1);
ans += x;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,1,4};
cout << (ob.subarraysWithKDistinct(v, 3));
}輸入
{1,2,3,1,4}, 3輸出
4
更新於: 2020-06-04
183 次檢視
廣告