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++算法设计的学习有所帮助。

赞 (0)

相关推荐

  • C++实现八皇后问题的方法

    本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没

  • C++线程池的简单实现方法

    本文以实例形式较为详细的讲述了C++线程池的简单实现方法.分享给大家供大家参考之用.具体方法如下: 一.几个基本的线程函数: 1.线程操纵函数: int pthread_create(pthread_t *tidp, const pthread_attr_t *attr, (void*)(*start_rtn)(void *), void *arg); //创建 void pthread_exit(void *retval); //终止自身 int pthread_cancel(pthread_

  • C++实现string存取二进制数据的方法

    本文实例讲述了C++实现string存取二进制数据的方法,分享给大家供大家参考.具体方法分析如下: 一般来说,STL的string很强大,用起来也感觉很舒服,这段时间在代码中涉及到了用string存取二进制数据的问题,这里记录一下,以供以后参考. 首先提一下STL中string的参考资料:http://www.cplusplus.com/reference/string/string/ ,不懂的朋友可以看下. 在数据传输中,二进制数据的buffer一般用系统预设的大数组进行存储,而不是STL的s

  • C++实现二叉树非递归遍历方法实例总结

    一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的.现举一个非递归遍历的方法如下,供大家参考. 具体代码如下: class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> out; stack<TreeNode*> s; s.push(root); while(!s.empty()

  • C++常用字符串分割方法实例汇总

    C++常用字符串分割方法实例汇总

    本文实例汇总了C++常用字符串分割方法,分享给大家供大家参考.具体分析如下: 我们在编程的时候经常会碰到字符串分割的问题,这里总结下,也方便我们以后查询使用. 一.用strtok函数进行字符串分割 原型: char *strtok(char *str, const char *delim); 功能:分解字符串为一组字符串. 参数说明:str为要分解的字符串,delim为分隔符字符串. 返回值:从str开头开始的一个个被分割的串.当没有被分割的串时则返回NULL. 其它:strtok函数线程不安全

  • C++链表倒序实现方法

    本文通过一个实例展示了C++实现链表倒序的方法,对于C++数据结构的学习有很好的参考借鉴价值.具体方法如下: 首先,C++链表倒序的难点在于如何一个个地修改.虽然不是数组,但是大概思想是一样的,所以可以用一个for循序,一个游标对应for循环里面的 i,只不过要记得前一个节点和后一个节点,尤其是后一个,因为修改之后就访问不到后面的,所以要记录.for每一个循环只改变所指向的那个节点的指针,这样既不会乱套了. 用一个for循环就非常好理解了,实例代码如下所示: #include <iostream

  • C++循环链表之约瑟夫环的实现方法

    本文实例形式展示了C++实现循环链表中约瑟夫环的方法,分享给大家供大家参考之用.具体方法如下: 主要功能代码如下: #include <iostream> using namespace std; typedef struct student { int data; struct student* next; }node,*LinkList; //约瑟夫环 void printfList(LinkList head){ LinkList p=head; if (head!=NULL) { do

  • C++实现二叉树遍历序列的求解方法

    C++实现二叉树遍历序列的求解方法

    本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树 如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序

  • C++实现raw_input的方法

    本文实例讲述了C++实现raw_input的方法,分享给大家供大家参考.具体方法分析如下: 用惯了Python,现在写C++的代码感觉有点不太顺畅.今天就来实例演示一下C++实现raw_input的方法. 用过Python的朋友知道,Python中有个raw_input,可以如下使用: print raw_input("Input a number : ") 一个函数内既有输入提示,又有返回值,用起来着实方便.可现在的问题是在C++中,我也想这么干,怎么办?其实,写一个函数也可以轻松实

  • 提高C++程序运行效率的10个简单方法

    本文以C/C++程序为例讲述了程序运行效率的10个简单方法,分享给大家供大家参考之用.具体分析如下: 对于每一个程序员来说,程序的运行效率都是一个值得重视,并为之付出努力的问题.但是程序性能的优化也是一门复杂的学问,需要很多的知识,然而并不是每个程序员都具备这样的知识,而且论述如何优化程序提高程序运行效率的书籍也很少.但是这并不等于我们可以忽略程序的运行效率,下面就介绍一下本人积累的一些简单实用的提高程序运行效率的方法,希望对大家有所帮助. 一.尽量减少值传递,多用引用来传递参数. 至于其中的原

  • C++深度优先搜索的实现方法

    C++深度优先搜索的实现方法

    本文实例讲述了图的遍历中深度优先搜索的C++实现方法,是一种非常重要的算法,具体实现方法如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次.注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历.图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search). 一.深度优先搜索(DFS)的算法思想 深度优先搜索算法所遵循的搜索策略是尽可能"深&

  • C++设计模式之工厂方法模式

    C++设计模式之工厂方法模式

    问题描述 之前讲到了C++设计模式--简单工厂模式,由于简单工厂模式的局限性,比如:工厂现在能生产ProductA.ProductB和ProductC三种产品了,此时,需要增加生产ProductD产品:那么,首先是不是需要在产品枚举类型中添加新的产品类型标识,然后,修改Factory类中的switch结构代码.是的,这种对代码的修改,对原有代码的改动量较大,易产生编码上的错误(虽然很简单,如果工程大了,出错也是在所难免的!!!).这种对代码的修改是最原始,最野蛮的修改,本质上不能称之为对代码的扩

  • C++实现第K顺序统计量的求解方法

    C++实现第K顺序统计量的求解方法

    一个n个元素组成的集合中,第K个顺序统计量(Order Statistic)指的是该集合中第K小的元素,我们这里要讨论的是如何在线性时间(linear time)里找出一个数组的第K个顺序统计量.该问题的算法对于C++程序员来说有一定的借鉴价值.具体如下: 一.问题描述: 问题:给定一个含有n个元素的无序数组,找出第k小的元素. k = 1 :最小值 k = n :最大值 k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ :中位数 找最大值或最小值很简单,只需要遍历一次数组并记录下最大值或最

随机推荐