C++求逆序对的方法

软件编程 C 语言 分类:[default] 更新日期: 2016-04-22
这篇文章主要介绍了C++求逆序对的方法,包含了字符串常见的操作方法,是非常实用的技巧,需要的朋友可以参考下

本文实例讲述了C++求逆序对的方法,分享给大家供大家参考之用。具体实现方法如下:

#include <iostream>
#include <vector>

using namespace std;

int array[] = {3, 9, 7, 4, 5, 2};
const int size = sizeof array / sizeof *array;
int temp[size];
//int numbers[size];

int reversePair(int *numbers, int start, int last, int &index, int &count)
{
 if(start == last)
 return 0;
 int mid = (last - start) / 2 + start;
 reversePair(numbers, start, mid, index, count);
 reversePair(numbers, mid + 1, last, index, count);

 for(int i = start; i <= last; i++)
 temp[i] = numbers[i];
 int index1 = start, index2 = mid + 1;
 index = start;
 while(index1 <= mid && index2 <= last) {
 if(temp[index1] > temp[index2]) {
  numbers[index] = temp[index2];
  count += mid - index1 + 1;
  index++;
  index2++;
 } else if(temp[index1] == temp[index2]) {
  numbers[index] = temp[index1];
  index++;
  index1++;
  index2++;
 } else if(temp[index1] < temp[index2]) {
  numbers[index] = temp[index1];
  index++;
  index1++;
 }
 }

 if(index1 <= mid) {
 while(index1 <= mid) {
  numbers[index] = temp[index1];
  index++;
  index1++;
 }
 } else {
 while(index2 <= last) {
  numbers[index] = temp[index2];
  index++;
  index2++;
 }
 }
 return count;
}

void main()
{
 int count = 0;
 int index = 0;
 reversePair(array, 0, size - 1, index, count);

 cout << "count = " << count << endl;
}

希望本文所述对大家C++算法设计的学习有所帮助。


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • Bootstrap中文本框的宽度变窄并且加入一副验证码图片的实现方法
    Bootstrap中文本框的宽度变窄并且加入一副验证码图片的实现方法
    这篇文章主要介绍了Bootstrap中文本框的宽度变窄并且加入一副验证码图片的实现方法的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下今天项目经理刚交给一个活儿,要我实现这样一个功能:要实现的是验证码文本框变窄一点,然后右边加入一副验证码图片,并且在响应式布局的情况下在移动端访问的时候验证码图片能保持和验证码文本框在同一行,这个怎么做?难为了半天 ...
  • 正则表达式性能优化方法高效正则表达式书写
    正则表达式性能优化方法高效正则表达式书写
    这里说的正则表达式优化,主要是针对目前常用的NFA模式正则表达式这里说的正则表达式优化,主要是针对目前常用的NFA模式正则表达式,详细可以参考:正则表达式匹配解析过程探讨分析(正则表达式匹配原理).从上面例子,我们可以推断出,影响NFA类正则表达式(常见语言:GNU Emacs,Java,ergp,less,more,.NET语言, PCRE library ...
  • Python中在脚本中引用其他文件函数的实现方法
    下面小编就为大家带来一篇Python中在脚本中引用其他文件函数的实现方法.小编觉得挺不错的,现在就分享给大家,也给大家做个参考.一起跟随小编过来看看吧在导入文件的时候,Python只搜索当前脚本所在的目录,加载(entry-point)入口脚本运行目录和sys.path中包含的路径例如包的安装地址.所以如果要在当前脚本引用其他文件,除了将文件放在和脚本同一目 ...
  • asp.net及javascript判断是否手机访问的方法
    这篇文章主要介绍了asp.net及javascript判断是否手机访问的方法,结合实例形式对比分析了asp.net及javascript实现判断访问端类型的相关技巧,需要的朋友可以参考下本文实例讲述了asp.net及javascript判断是否手机访问的方法.分享给大家供大家参考,具体如下: /// <summary> /// 判断手机用户Use ...
  • asp画中画广告插入在每篇文章中的实现方法
    这篇文章主要介绍了asp画中画广告插入在每篇文章中的实现方法,需要的朋友可以参考下尽管很多人给出了给每篇文章加上画中画广告的方法,但是这些所谓的方法,都不能真正地实现文字环绕在广告周围的"画中画"效果,只能左对其或者右对齐.现在要讨论的这个方法才能真正实现像新浪网.搜狐网那样的画中画广告效果. 首先说一下错误的div+CSS方法,希望大家 ...
  • JavaWeb实现图形报表折线图的方法
    这篇文章主要介绍了JavaWeb实现图形报表折线图的方法,涉及JSP包的引用.图形操作.配置文件设置及字符串操作技巧,需要的朋友可以参考下本文实例讲述了JavaWeb实现图形报表折线图的方法.分享给大家供大家参考,具体如下: 步骤说明: 1. 导入log4j.jar,jfreechart-0.9.18.jar,jdom.jar,jcommon-0.9.3.j ...
猜你喜欢