剑指Offer34 数组中的逆序对
2024-10-12 19:23:00
/*************************************************************************
> File Name: 34_InversePairsInArray.c
> Author: Juntaran
> Mail: JuntaranMail@gmail.com
> Created Time: 2016年09月02日 星期五 20时05分05秒
************************************************************************/ #include <stdio.h>
#include <malloc.h> int InversePairsCore(int* nums, int* copy, int left, int right)
{
if (left == right)
{
copy[left] = copy[right];
return ;
}
int newlength = (right - left) / ; // 递归
int leftCount = InversePairsCore(copy, nums, left, left+newlength);
int rightCount = InversePairsCore(copy, nums, left+newlength+, right); // i初始化为前半段最后一个数字下标
int i = left + newlength;
// j初始化为后半段最后一个数字下标
int j = right; int indexCopy = right;
int count = ; while (i>=left && j>=left+newlength+)
{
if (nums[i] > nums[j])
{
copy[indexCopy--] = nums[i--];
count += j - left - newlength;
}
else
{
copy[indexCopy--] = nums[j--];
}
} for (i; i >= left; --i)
copy[indexCopy--] = nums[i];
for (j; j>=left+newlength+; --j)
copy[indexCopy--] = nums[j]; return leftCount + rightCount + count;
} int InversePairs(int* nums, int length)
{
if (nums==NULL || length<=)
return -; int* copy = (int*)malloc(sizeof(int)*length);
for (int i = ; i < length; ++i)
copy[i] = nums[i]; int count = InversePairsCore(nums, copy, , length-);
delete[] copy; return count;
} int main()
{
int nums[] = {,,,};
int length = ;
int ret = InversePairs(nums, length);
printf("%d\n", ret);
}
最新文章
- Android随笔之——Activity中启动另一应用
- ASP.NET Core中的ActionFilter与DI
- iotop命令
- 完成端口CreateIoCompletionPort编写高性能的网络模型程序
- MySQL: InnoDB 还是 MyISAM?
- WordPress主题制作教程9:文章形式
- 软件开发中的单一职责(转至INFOQ)
- JDk 内部分工具 简述
- Fresco 多图加载之ResizeOptions
- PHP7新功能及语法变化总结
- Intent之间无法传递大数据的替代方法
- Alpha第八天
- Cache高速缓冲存储器
- opencv学习系列:连通域参考处理
- InfluxDB时序数据库应用场景
- Jmeter常用脚本开发之SOAP/XML-RPC Request
- 一:理解ASP.NET的运行机制(例:通过HttpModule来计算页面执行时间)
- JS深拷贝继承
- 修改多渠道打包的App名
- Kafka 练习题