英文:
Most efficient way to calculate count of consecutive buildings that are shorter than current buildings
问题
在下面的代码片段中,该程序计算了连续建筑物中低于当前建筑物的数量。它从初始计数0开始,对于每栋低于当前建筑物的建筑物,将计数加1。当遇到高于或等于的建筑物时,将当前计数添加到总计数中并将计数重置为0。
但是,这个解决方案的时间复杂度是O(n^2),如果建筑物数量较多,效率不高。如何改进这个解决方案呢?任何建议都将对我有所帮助。
注意:建筑物大小的数组范围是>=6且<=80000,建筑物的高度范围是1到100000000。
英文:
In below code snippet The program calculates the count of consecutive buildings that are shorter than the current building. It starts with an initial count of 0 and adds 1 to the count for each building that is shorter than the current building. When it encounters a building that is taller or equal, it adds the current count to the total count and resets the count to 0.
but this solution's time complexity is o (n2) and doesn't look more effective if no. of building is more . How to improve this solution ? Any suggested pointer will be helpful for me.
Note: Array of building size >=6 and <=80000 and height of building can be 1 to 100000000
#include <iostream>
using namespace std;
int main()
{
cout<<"Hello World";
int N;
int count = 0;
int total_count = 0;
int output ;
int H [] = {5,3,4,2,6,1};
int size = sizeof(H) / sizeof(H[0]);
for (int i = 0; i < size ; i++)
{
for (int j = i+1 ; j < size ; j++)
{
if (H[i] > H[j])
{
count ++;
std::cout<<"count value = " << count << H[i] << std::endl;
}
else
{
total_count = total_count + count ;
count = 0;
break;
}
}
}
// Write the code
total_count = total_count + count ;
output = total_count;
cout << "output = "<<output << endl; // Output right answer
return 0;
}
答案1
得分: 1
这是一个O(n)的方法。
主要思想是我们不关心每个样本中较小元素的数量,而是它们的总和。
这使得另一种方法成为可能。对于每个新元素,我们计算高于当前元素的元素数量,并将它们存储在一个栈中。
因此,对于每个新元素,我们会移除那些较小或相等的元素,然后将栈的大小添加到总计中。新元素随后添加到栈中。
这个算法的复杂度为O(n),因为每个元素只会被添加或移除一次。
以下代码将新方法的结果与暴力O(n^2)方法进行了比较。
#include <iostream>
#include <vector>
#include <stack>
// 暴力方法
int count_bf (const std::vector<int>& H) {
int size = H.size();
int total_count = 0;
for (int i = 0; i < size ; i++) {
for (int j = i+1 ; j < size ; j++) {
if (H[i] > H[j]){
total_count ++;
} else {
break;
}
}
}
return total_count;
}
// 快速方法
int count_fast (const std::vector<int>& H) {
int size = H.size();
int total_count = 0;
std::stack<int> lifo;
for (int i = 0; i < size ; i++) {
while (!lifo.empty() && (lifo.top() <= H[i])) {
lifo.pop();
}
total_count += lifo.size();
lifo.push(H[i]);
}
return total_count;
}
int main() {
std::vector<int> H = {5, 3, 4, 2, 6, 1, 13, 15, 17, 14, 13};
int total_count = count_bf(H);
std::cout << "output brute-force method = " << total_count << std::endl;
total_count = count_fast(H);
std::cout << "output fast method = " << total_count << std::endl;
return 0;
}
希望这有助于您理解代码的内容。
英文:
This is an O(n) method
The main idea is that we are not interested to count the numbers of lower elements of each sample, but the total sum of them.
This allows another approach. For each new element, we count the number of elements which are higher than the current one, which are memorized in a stack.
Therefore, for each new element, we suppress the elements which are lower or equal, and then add the size of the stack to the total count.
The new element is then added to the stack.
Ths complexity is O(n) because each element is added or removed only once to/from the stack.
The following code compares the result of the new approach with the brute-force O(n^2) one.
#include <iostream>
#include <vector>
#include <stack>
// Brute-force (OP) method
int count_bf (const std::vector<int>& H) {
int size = H.size();
int total_count = 0;
for (int i = 0; i < size ; i++) {
for (int j = i+1 ; j < size ; j++) {
if (H[i] > H[j]){
total_count ++;
} else {
break;
}
}
}
return total_count;
}
// Fast method
int count_fast (const std::vector<int>& H) {
int size = H.size();
int total_count = 0;
std::stack<int> lifo;
for (int i = 0; i < size ; i++) {
while (!lifo.empty() && (lifo.top() <= H[i])) {
lifo.pop();
}
total_count += lifo.size();
lifo.push(H[i]);
}
return total_count;
}
int main() {
std::vector<int> H = {5, 3, 4, 2, 6, 1, 13, 15, 17, 14, 13};
int total_count = count_bf(H);
std::cout << "output brute-force method = "<< total_count << std::endl;
total_count = count_fast(H);
std::cout << "output fast method = "<< total_count << std::endl;
return 0;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论