黑客地球泡沫排序
Hackerearth bubbleSort
在 Hackerearth 中,我尝试解决冒泡排序交换计数问题。我的输出总是与正确的 output.for 示例不同;
我的输出是 2475,正确的输出是 2788
#include <iostream>
using namespace std;
int main()
{
int *A,tm,times=0;
cin >> tm;
A = new int[tm];
for(int i = 0; i<tm;i++) {cin >> A[i];}
int temp;
for(int i = 0; i<tm;i++){
for(int j = 0; j < tm-i-1;j++){
if(A[j] > A[j+1]){
times++;;
temp = A[j];
A[j] = A[j+1];
A[j] = temp;
}
}
}
cout << times;
return 0;
}
是我做错了什么还是正确的输出有误?
在交换逻辑中,代替
A[j]=temp;
写
A[j+1]=temp;
在外层 for 循环中,i<tm-1
而不是 i<tm
可能这无关紧要,但可以找到复杂度更高的反转数。此解决方案将需要 O(n^2)。它可以在 O(nlogn) 时间复杂度内完成。这个想法是使用 merge 排序,在合并状态下你已经知道有多少值来自一个值 greater/smaller 而无需实际计算它们。合并时,如果右子数组的一个值更大,则它右边的所有其他值也都更大。您只需要计算正确的值有多少。这里提供了详细而愉快的解释。
在 Hackerearth 中,我尝试解决冒泡排序交换计数问题。我的输出总是与正确的 output.for 示例不同;
我的输出是 2475,正确的输出是 2788
#include <iostream>
using namespace std;
int main()
{
int *A,tm,times=0;
cin >> tm;
A = new int[tm];
for(int i = 0; i<tm;i++) {cin >> A[i];}
int temp;
for(int i = 0; i<tm;i++){
for(int j = 0; j < tm-i-1;j++){
if(A[j] > A[j+1]){
times++;;
temp = A[j];
A[j] = A[j+1];
A[j] = temp;
}
}
}
cout << times;
return 0;
}
是我做错了什么还是正确的输出有误?
在交换逻辑中,代替
A[j]=temp;
写
A[j+1]=temp;
在外层 for 循环中,i<tm-1
而不是 i<tm
可能这无关紧要,但可以找到复杂度更高的反转数。此解决方案将需要 O(n^2)。它可以在 O(nlogn) 时间复杂度内完成。这个想法是使用 merge 排序,在合并状态下你已经知道有多少值来自一个值 greater/smaller 而无需实际计算它们。合并时,如果右子数组的一个值更大,则它右边的所有其他值也都更大。您只需要计算正确的值有多少。这里提供了详细而愉快的解释。