文档章节

count_inversions in an integer list

ludlows
 ludlows
发布于 2014/10/07 22:54
字数 98
阅读 1
收藏 0
点赞 0
评论 0

count = 0

def merge_sort(li):

    if len(li) < 2: return li 
    m = len(li) / 2 
    return merge(merge_sort(li[:m]), merge_sort(li[m:])) 

def merge(l, r):
    global count
    result = [] 
    i = j = 0 
    while i < len(l) and j < len(r): 
        if l[i] < r[j]: 
            result.append(l[i])
            i += 1 
        else: 
            result.append(r[j])
            count = count + (len(l) - i)
            j += 1
    result.extend(l[i:]) 
    result.extend(r[j:]) 
    return result
filename = 'Integer.txt'
unsorted = []
inFile = open(filename, 'r')
lines = inFile.readlines()
for i in lines:
    content = i.strip('\n')
    unsorted.append(int(content))



merge_sort(unsorted)
print count


© 著作权归作者所有

共有 人打赏支持
ludlows
粉丝 0
博文 15
码字总数 4195
作品 0
海淀
程序员
POJ1007·DNA Sorting

一道水题,算法也没用多么复杂的,但在G++环境下提交成功,C++会报编译不过的错误。 Description One measure of unsortedness'' in a sequence is the number of pairs of entries that are...

OldPanda ⋅ 2012/06/01 ⋅ 4

POJ 1007 -- DNA Sorting

DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 94974 Accepted: 38197 Description One measure of unsortedness'' in a sequence is the number of pairs of en......

圣洁之子 ⋅ 2016/05/27 ⋅ 0

出现次数较多的k个数 Top K Frequent Words

问题: Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequen......

叶枫啦啦 ⋅ 02/01 ⋅ 0

Java里面如何求两个集合的交集

在Python里,或许我们没有这个烦恼,因为python里已经为我们提供了intersection这样的方法。 但是在Java里,就需要我们动一番脑筋了。这里浓重推荐下apache的CollectionUtils工具类。 方法签...

Airship ⋅ 2015/02/12 ⋅ 2

关联规则FP树算法java实现

首先,定义一个节点: package algorithm.correlation.fptree; import java.util.ArrayList; import java.util.List; /** * 树节点模型 * Title: UCAS <br> * Description: <br> * Date: 201......

xyfengbo ⋅ 2014/06/23 ⋅ 0

Spring Data Jpa 查询返回自定义对象

http://www.wangyongkui.com/java-jpa-query/ Spring Data Jpa 查询返回自定义对象 发表回复 转载请注明出处:http://www.wangyongkui.com/java-jpa-query。 今天使用Jpa遇到一个问题,发现查...

nibilly ⋅ 2015/12/23 ⋅ 2

Redis之KEY操作命令 【学习笔记】

开启服务 $sudo ./src/redis-server & 键操作 *定义并赋值变量苹果的数量$ redis-cli set dangcheng::apple::count 152OK *获取刚才的苹果数量$ redis-cli get dangcheng::apple::count"152......

党程V ⋅ 2014/12/05 ⋅ 0

hibernate中查询全部记录返回list,但是list.get(0)会报错

private int getTotalRow(){ Session session=HibernateSessionFactory.getSession(); Query query=session.createQuery("select count(*) from House"); List list=query.list(); int count......

星空下*许愿 ⋅ 2012/08/27 ⋅ 15

数独优化

数独优化 问题已用红色字体表示,请大神帮小弟解答一下 package idea; import java.util.ArrayList; public class Sodukus2 { private int[] special = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; pri......

lzhphantom ⋅ 2017/10/23 ⋅ 3

Top K Frequent Words

问题: Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequen......

叶枫啦啦 ⋅ 01/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Thrift RPC实战(二) Thrift 网络服务模型

TServer类层次体系 TSimpleServer/TThreadPoolServer是阻塞服务模型 TNonblockingServer/THsHaServer/TThreadedSelectotServer是非阻塞服务模型(NIO) 1 TServer抽象类的定义 内部静态类Args的...

lemonLove ⋅ 15分钟前 ⋅ 0

vim命令用法

第五章 vim命令 vim和vi几乎是一样的,唯一的区别就是当编辑一个文本时,使用vi不会显示颜色,而使用vim会显示颜色。 vim有三个模式:一般模式,编辑模式,命令模式。 系统最小化安装时没有安...

弓正 ⋅ 17分钟前 ⋅ 0

MyBatis源码解读之配置

1. 目的 本文主要介绍MyBatis配置文件解析,通过源码解读mybatis-config.xml(官方默认命名)、Mapper.xml 与Java对象的映射。 2. MyBatis结构 查看大图 MyBatis结构图,原图实在太模糊了,所以...

无忌 ⋅ 21分钟前 ⋅ 0

Ignite的jdbc与网格的连接方式的查询性能对比

环境: 数据量100万 Ignite2.5 Windows10 8g jdbc方式连接 import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.ResultSet; i......

仔仔1993 ⋅ 35分钟前 ⋅ 0

收集自网络的wordpress 分页导航的代码教程(全网最全版)

wordpress 分页导航是用来切换文章的一个功能,添加了 wordpress 分页导航后,用户即可自由到达指定的页面数浏览分类文章,而这样的一个很简单功能却有很多朋友在用插件:WP-PageNavi,插件的...

Rhymo-Wu ⋅ 51分钟前 ⋅ 0

微服务 WildFly Swarm 入门

Hello World 就像前面章节中的其他框架一样,我们希望添加一些基本的 Hello-world 功能,然后在其上逐步添加更多的功能。让我们从在我们的项目中创建一个 HolaResources 开始。您可以使用您的...

woshixin ⋅ 58分钟前 ⋅ 0

Maven的安装和Eclipse的配置

1. 下载Maven 下载地址 2. 解压压缩包,放到自己习惯的硬盘中 此处我将其放到了 D:\Tools 目录下。 3. 配置环境变量 右键此电脑 -> 属性 -> 高级系统设置 -> 环境变量。 在系统变量中新建,变...

影狼 ⋅ 今天 ⋅ 0

python pip使用国内镜像的方法

国内源 清华:https://pypi.tuna.tsinghua.edu.cn/simple 阿里云:http://mirrors.aliyun.com/pypi/simple/ 中国科技大学 https://pypi.mirrors.ustc.edu.cn/simple/ 华中理工大学:http://......

良言 ⋅ 今天 ⋅ 0

对于url变化的spa应该如何使用微信jssdk

使用vue单页面碰上微信jssdk config验证失败的坑。第一次成功 之后切换页面全部失败,找到了解决方法,第一次验证成功后保存验证信息 切换页面时验证信息直接拿来用,加一个wx.error() 失败时...

孙冠峰 ⋅ 今天 ⋅ 0

Spring Cloud Gateway 一般集成

SCF发布,带来很多新东西,不过少了点教程,打开方式又和以前的不一样,比如这个SCG,压根就没有入门指导,所以这里写一个,以备后用。 一、集成 pom.xml <dependency> <groupI...

kut ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部