c++ - 如果数组长度为 100000,则使用归并排序计算反转会给出负数
问题描述
我仍然是编程的初学者,我正在学习在线课程(算法)
练习题之一是计算包含 100000 个随机排序的数字的文件中的反转次数。我已经在小型数据集上尝试过这段代码,它工作得很好,但是当传递实际数据集时,它给出了负数的反转计数。尝试了来自不同平台的各种解决方案,但仍然无法解决。
所以这是我的代码
#include "stdafx.h"
#include <iostream>;
#include <conio.h>:
#include <fstream>
using namespace std;
long merge(int a[], int start, int mid, int end)
int i = start;
int j = mid + 1;
int k = start;
int inversion=0;
int temp[100000];
while (i <= mid && j <= end)
{
if (a[i] < a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
inversion =inversion + (mid - i);
}
}
while (i <= mid)
{
temp[k++] = a[i++];
}
while (j <= end)
{
temp[k++] = a[j++];
}
for (int i = start; i <= end; i++)
{
a[i] = temp[i];
}
return inversion;
long Msort(int a[], int start,int end)
{
if (start >= end)
{
return 0;
}
int inversion = 0;
int mid = (start + end) / 2;
inversion += Msort(a, start, mid);
inversion += Msort(a, mid + 1, end);
inversion += merge(a, start, mid, end)
return inversion;
}
long ReadFromFile(char FileName[], int storage[],int n)
{
int b;
int count=0;
ifstream get(FileName);
if (!get)
{
cout << "no file found";
}
while (!get.eof())
{
get >> storage[count];
count++;
}
b = count;
return b;
}
int main()
{
int valuescount = 0;
int arr[100000];
char filename[] = { "file.txt" };
long n = sizeof(arr) / sizeof(arr[0]);
valuescount=ReadFromFile(filename, arr,n);
int no_Of_Inversions = Msort(arr, 0, valuescount -1);
cout << endl << "No of inversions are" << '\t' << no_Of_Inversions <<'\t';
cout <<endl<< "Total no of array values sorted"<< valuescount<<endl;
system("pause");
}
`
解决方案
您的代码问题与输入大小没有直接关系。相反,以间接方式,您发现的负数反转是inversion
函数变量溢出的结果merge
。
考虑您的输入大小的情况N = 100000
。如果这个数字数组按降序排序,那么该数组中的所有有序对都是反转的。换句话说,会有N * (N-1) / 2
倒置被计算在内。您可能已经注意到,该值略高于unsigned int
类型的界限。因此,当您尝试在 int 类型的变量中计算该值时,会发生溢出,从而导致否定结果。
要解决此问题,您应该在函数中将变量的类型inversion
从int
更改为和。(您还应该更新函数的返回类型和)当然,您也应该将函数中调用的返回值分配给类型变量。换句话说,将变量的类型也更改为 long long。long long
merge
Msort
merge
Msort
Msort
main
long long
no_Of_Inversions
推荐阅读
- c# - Azure 出现启动应用程序错误
- lua - 初学者lua:检查数组的值
- ruby-on-rails - 使用 amazon sdk gem 时的加载问题
- mongodb - 聚合,从 2 个集合中查找并提取结果
- algorithm - 检查矩阵中元素邻居的最佳方法
- ruby-on-rails - 如何在 Rails 中使用 after_create 回调方法?
- javascript - 如果密钥存在如何更新 - 续集
- java - 流利的等待不能在硒中工作以获取角度
- android - 使用渐进式 Web 应用程序时 Android 软菜单重叠
- ios - 如何在Swift中点击可扩展表格单元格时自动隐藏键盘