資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚科學
法律科學使用 C++ 獲取 n 個範圍中的最大整數
在該問題中，我們給出了 N 個範圍。我們的任務是n 個範圍中出現的最大整數。
對於所有範圍的起始和結束值。我們需要找出出現次數最多的值。
我們舉個例子來理解該問題：
輸入
S1 = 1, E1 = 3 S2 = 2, E2 = 6 S3 = 3, E3 = 4
輸出
2
解決方法
解決該問題的簡單方法是使用雜湊，我們將使用雜湊表來統計所有成員及其計數。我們將遍歷所有範圍並在雜湊表中儲存計數，然後我們將找到最大計數。
線性時間內解決問題的另一種方法是使用範圍陣列。在此陣列中，我們將透過將 1 新增到所有範圍的起始值並從其中減去 1 來更新所有範圍的結束值。這將找到字首和並找到最大字首和值。
示例
展示我們解決方案工作原理的程式
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int findMaxOccrEle(int L[], int R[], int n){
int occurenceConut[MAX];
memset(occurenceConut, 0, sizeof occurenceConut);
int maxi = -1;
for (int i = 0; i < n; i++) {
occurenceConut[L[i]] += 1;
occurenceConut[R[i] + 1];
if(R[i]>maxi){
maxi=R[i];
}
}
int prefSum = occurenceConut[0],maxEleIndex;
for (int i = 1; i < maxi+1; i++) {
occurenceConut[i] += occurenceConut[i - 1];
if (prefSum < occurenceConut[i]) {
prefSum = occurenceConut[i];
maxEleIndex = i;
}
}
return maxEleIndex;
}
int main(){
int L[] = { 1, 2, 3 };
int R[] = { 3, 6, 4 };
int n = sizeof(L) / sizeof(L[0]);
cout<<"The maximum occurred integer in the range is "<<findMaxOccrEle(L, R, n);
return 0;
}輸出
The maximum occurred integer in the range is 3
更新於：2022 年 2 月 14 日
396 次檢視
廣告