資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++程式中字尾中不同整數個數的查詢
在這個問題中，我們給定一個包含 n 個整數值的陣列 arr[]。以及 Q 個查詢，每個查詢包含一個整數 k。我們的任務是建立一個程式來解決字尾中不同整數個數的查詢。
問題描述 − 我們需要解決字尾中不同整數的查詢。對於每個查詢，我們需要找到從 k 到 n 的唯一元素的數量，即計算 arr[k] 到 arr[n] 中唯一元素的數量。
所取陣列從 1 開始索引。
讓我們舉個例子來理解這個問題，
輸入
arr[ ] = {5, 1, 2, 1, 6 , 5}, n = 6, Q = 3, query = {1, 3, 4}輸出
4 4 3
解釋
For Query 1: k = 1, N = 6, Count of elements from arr[1] to arr[6]. Count = 4. For Query 2: k = 3, N = 6, Count of elements from arr[3] to arr[6]. Count = 4 For Query 3: k = 4, N = 6, Count of elements from arr[4] to arr[6]. Count = 3
解決方案方法
解決此問題的簡單方法是從索引 k 到 n 開始解決每個查詢。並計算陣列的所有唯一元素，並返回每個查詢的計數。
有效解決方案
解決此問題的有效方法是使用預先計算的資料結構，該結構儲存從 (n-1) 到 0 的索引的唯一計數。這是透過使用無序集合來消除重複元素的新增來完成的。我們甚至可以使用輔助陣列來進行出現次數計數。
我們將從最後到第 k 個元素開始將陣列的元素新增到我們的資料結構中，然後查詢資料結構中元素的數量（在第 k 個索引處的陣列值的情況下）。
程式說明我們解決方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
unordered_set<int> uniqueInts;
int distIntCount[n + 1];
for (int i = n - 1; i >= 0; i--) {
uniqueInts.insert(arr[i]);
distIntCount[i + 1] = uniqueInts.size();
}
for (int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": the number of distinct integers in Suffix is "<<distIntCount[queries[i]]<<endl;
}
int main() {
int n = 6, Q = 3;
int arr[n] = {5, 1, 2, 1, 6, 5};
int queries[Q] = {1, 3, 4};
solveQueries_DistInt(n, arr, Q, queries);
return 0;
}輸出
For Query 1: the number of distinct integers in Suffix is 4 For Query 2: the number of distinct integers in Suffix is 4 For Query 3: the number of distinct integers in Suffix is 3
更新於: 2020-12-22
202 次檢視
廣告